I am implementing the Shunting-Yard algorithm and evaluating the results This is a reference-based implementation using Nodes (one for operators and one for operands) and stacks (one for operators and one for operands).
The input file contains (just the first few lines):
5
5-3
5*(3+4)
7*3+5*6
2+5*(7+8)/3
The output:
53 = 53
53513 = 1
535152
Exception in thread "main" java.lang.StringIndexOutOfBoundsException:
String index out of range: 7
at java.lang.String.charAt(String.java:646)
at LabIII.main(LabIII.java:48)
Process completed.
Main:
public class LabIII
{
public static String expr;
public static String line;
public static void main(String[] args) throws IOException
{
try
{
BufferedReader input = new BufferedReader(new FileReader("input.txt")); // Create input reader
char token;
int tokenI;
char popOp;
int popInt1;
int popInt2;
int result;
while ((line = input.readLine()) != null) // While the input file still has a line with characters
{
operatorStack opStack = new operatorStack(); // Initalize the operator stack
opStack.push(';');
operandStack intStack = new operandStack();
expr = line;
int count = 1;
while(count <= expr.length())
{
int index = count - 1;
if(Character.isDigit(expr.charAt(index))) // If token is an operand
{
tokenI = expr.charAt(index);
System.out.print(tokenI);
intStack.push(tokenI);
count++;
}
else
{
token = expr.charAt(count);
if(token == ')')
{
while(opStack.peek() != '(')
{
popOp = opStack.pop();
System.out.print(popOp);
popInt1 = intStack.pop();
popInt2 = intStack.pop();
result = evaluate(popInt1, popInt2, popOp);
intStack.push(result);
}
opStack.pop(); // Pop the "(" and discard it
count++;
}
else
{
while(inputPriority(token) <= stackPriority(opStack.peek()))
{
popOp = opStack.pop();
System.out.print(popOp);
popInt1 = intStack.pop();
popInt2 = intStack.pop();
result = evaluate(popInt1, popInt2, popOp);
intStack.push(result);
}
opStack.push(token);
count++;
}
}
}
while (opStack.peek() != ';')
{
popOp = opStack.pop();
System.out.print(popOp);
popInt1 = intStack.pop();
popInt2 = intStack.pop();
result = evaluate(popInt1, popInt2, popOp);
intStack.push(result);
}
System.out.print(" = " + intStack.pop());
System.out.println();
count = 0;
}
}
catch (IOException ex)
{
System.err.println("Exception:" + ex);
}
}
}
operandStack (also one for operatorStack. Same, just uses char instead of int):
public class operandStack
{
int integ;
NodeInt top;
NodeInt temp;
public operandStack() // Default constructor: empty stack
{
top = null;
}
public boolean isEmpty() // Returns true if the top of the stack is null
{
return top == null;
}
public void push(int integ) // Push an item onto the top of the stack
{
top = new NodeInt(integ, top);
}
public int pop()
{
NodeInt temp = top;
top = top.getNext();
return temp.getItem();
}
public void popAll()
{
top = null;
}
public int peek()
{
return top.getItem();
}
}
Node (also one for operands/integers):
public class Node{
private char item;
private Node next;
public Node(char newItem)
{
item = newItem;
next = null;
}
public Node(char newItem, Node nextNode)
{
item = newItem;
next = nextNode;
}
public char getItem()
{
return item;
}
public void setNext(Node nextNode)
{
next = nextNode;
}
public Node getNext()
{
return next;
}
}
The algorithm is as follows:
Initialize the operator stack to contain a ‘;’ (bottom of stack operator)
Get the first token
while the end of the expression is not reached
if the token is an operand then
Print the token
Push the operand onto the operand stack
else if the token is a ‘)’ then
while the top of the operator stack is not equal to ‘(’
Pop the operator stack
Print the operator
Pop the operand stack twice
Apply the designated operation to the two operands
Push the operation result onto the operand stack
end while
Pop the ‘(’ and discard it
else
while inputPriority(token) ≤ stackPriority(top of operator stack)
Pop the operator stack
Print the operator
Pop the operand stack twice
Apply the designated operation to the two operands
Push the operation result onto the operand stack
end while
Push the token onto the operator stack
Get the next token
end while
while the top of the operator stack is not equal to ‘;’
Pop the operator stack
Print the operator
Pop the operand stack twice
Apply the designated operation to the two operands
Push the operation result onto the operand stack
end while
Pop the operand stack and print the result
Any help is appreciated.
I figured out the issues. There were two other problems:
First, the input file had two extra empty lines at the end which was causing an exception.
Second, tokenI = expr.charAt(index) was assigning the ASCII value to tokenI (for instance, the input value of 5 was causing tokenI to be 53), so I simply needed to subtract 48 (the ASCII value for 0) to correct the issue. tokenI = expr.charAt(index) - 48 Everything else fell into place after that.
Also, as @EJP said, there was no need for both the "index" and "count" variables, so I removed "count" and just used "index."