Using Stack Data Type to Solve an Infix Expression
Hello! I have been given the assignment to use two ( 2 ) stacks to evaluate an infix expression. I cannot switch to postfix or prefix, then solve. It has to be a direct computation. I have been working on this for around 5 hours and cannot figure out why my code isn't working. When I run the program and type in an expression.... nothing happens. No errors, just no output. Any help pushing me in the right direction would be greatly appreciated. THANKS!
Code Java:
import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Pattern;
public class InfixEvaluation {
public static double evalz(String expression) {
Scanner console = new Scanner(expression);
Stack<Character> opStack = new Stack<Character>();
Stack<Double> valStack = new Stack<Double>();
String operator;
char topOperator;
char first;
double operandTwo;
double operandOne;
double result;
double next;
while(console.hasNext( )) {
}
if (console.hasNextDouble()) {
next = console.nextDouble();
valStack.push(next);
} else {
operator = console.next();
first = operator.charAt(0);
switch (first) {
case '^':
opStack.push(first);
break;
case '+':
case '-':
case '*':
case '/':
while (!opStack.isEmpty()
&& getPriority(first) <= getPriority(opStack.peek())) {
// Execute operator at top of opStack
topOperator = opStack.pop();
operandTwo = valStack.pop();
operandOne = valStack.pop();
if (topOperator == '*') result = operandOne * operandTwo;
else if (topOperator == '+') result = operandOne + operandTwo;
else if (topOperator == '-') result = operandOne - operandTwo;
else
throw new InfixException("Illegal symbol: " + topOperator);
valStack.push(result);
}
opStack.push(first);
break;
case '(':
opStack.push(first);
break;
case ')': // Stack is not empty if infix expression is valid
topOperator = opStack.pop();
while (topOperator != '(') {
operandTwo = valStack.pop();
operandOne = valStack.pop();
if (topOperator == '*') result = operandOne * operandTwo;
else if (topOperator == '+') result = operandOne + operandTwo;
else if (topOperator == '-') result = operandOne - operandTwo;
else
throw new InfixException("Illegal symbol: " + topOperator);
valStack.push(result);
topOperator = opStack.pop();
}
break;
default:
break;
}
}
while(!opStack.isEmpty()){
topOperator = opStack.pop();
operandTwo = valStack.pop();
operandOne = valStack.pop();
if (topOperator == '*') result = operandOne * operandTwo;
else if (topOperator == '+') result = operandOne + operandTwo;
else if (topOperator == '-') result = operandOne - operandTwo;
else
throw new InfixException("Illegal symbol: " + topOperator);
valStack.push(result);
}
double answer = valStack.peek();
return answer;
}
public static int getPriority(char first) {
if (first == '*' || first == '/')
return 1;
else if (first == '+' || first == '-')
return 2;
else if (first == '=')
return 3;
else
return Integer.MIN_VALUE;
}
public static final Pattern CHARACTER =
Pattern.compile("\\S.*?");
public static final Pattern UNSIGNED_DOUBLE =
Pattern.compile("((\\d+\\.?\\d*)|(\\.\\d+))([Ee][-+]?\\d+)?.*?");
}
And here is the MAIN:
MAIN:
Code Java:
import java.util.Scanner;
public class InfixConsole {
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
String line = null; // string to be evaluated
double answer; // result of evaluation
// Get next expression to be processed.
System.out.print("Enter an infix expression to be evaluated: ");
line = console.nextLine();
answer = InfixEvaluation.evalz(line);
// Output result.
System.out.println();
System.out.println("Result = " + answer);
}
}
I also have a small error exception class.. if I need to put that too please let me know. Thanks!
Re: Using Stack Data Type to Solve an Infix Expression
Code Java:
while(console.hasNext( )) {
}
You have a mismatched bracket so your program gets stuck in an infinite loop.
Re: Using Stack Data Type to Solve an Infix Expression
Alright.. wow, I didn't even notice that. I fixed it now I am receiving this error:
Exception in thread "main" java.util.EmptyStackException
at java.util.Stack.peek(Stack.java:85)
at java.util.Stack.pop(Stack.java:67)
at InfixEvaluation.evalz(InfixEvaluation.java:85)
at InfixConsole.main(InfixConsole.java:14)
Re: Using Stack Data Type to Solve an Infix Expression
It's not mismatched persay, but it's in the wrong place.
In your evalz method you have that piece of code that's intended to iterate through tokens of the expression, but instead of having the parsing code inside of it you have it after it. Simply move the closing brace to where it needs to be to include the parsing code in the while loop.
Suggestion: If you're using an IDE, see if there's an "auto-format" code function (In know Eclipse has one, hotkey = CTRL+SHIFT+F). It's much easier to check for problems like this if your code is properly formatted (much easier to read, too).
Re: Using Stack Data Type to Solve an Infix Expression
I would love to format it that way but my teacher is very strict on using "his" guidelines. So the way I have it formatted is the way HE thinks is best. But I did fix that stupid error on my part and am receiving the error above ^^^ (I edited the post).
Re: Using Stack Data Type to Solve an Infix Expression
This is the psuedocode provided by the teacher as well.
Code java:
Algorithm evaluateInfix (infix)
// Evaluates an infix expression.
operatorStack = a new empty stack
valueStack = a new empty stack
while (infix has characters left to process)
{
nextCharacter = next nonblank character of infix
switch (nextCharacter)
{
case variable:
valueStack.push (value of the variable nextCharacter)
break
case '^':
operatorStack.push (nextCharacter)
break
case '+':
case '-':
case '*':
case '/':
while (!operatorStack.isEmpty () and
precedence of nextCharacter <= precedence of operatorStack.peek ())
{
// Execute operator at top of operatorStack
topOperator = operatorStack.pop ()
operandTwo = valueStack.pop ()
operandOne = valueStack.pop ()
result = the result of the operation in topOperator and its operands
operandOne and operandTwo
valueStack.push (result)
}
operatorStack.push (nextCharacter)
break
case '(':
operatorStack.push (nextCharacter)
break
case ')': // stack is not empty if infix expression is valid
topOperator = operatorStack.pop ()
while (topOperator != '(')
{
operandTwo = valueStack.pop ()
operandOne = valueStack.pop ()
result = the result of the operation in topOperator and its operands
operandOne and operandTwo
valueStack.push (result)
topOperator = operatorStack.pop ()
}
break
default:
break
}
}
while (!operatorStack.isEmpty ())
{
topOperator = operatorStack.pop ()
operandTwo = valueStack.pop ()
operandOne = valueStack.pop ()
result = the result of the operation in topOperator and its operands
operandOne and operandTwo
valueStack.push (result)
}
return valueStack.peek ()
Re: Using Stack Data Type to Solve an Infix Expression
In Eclipse you can define how the auto-formatter works (I don't use the standard format). I can see a few places in your code where your formatting is inconsistent (unless that's really what your teacher wants, which I doubt).
It's possible that you can modify the auto-formatter to format as your teacher wants it to be formatted (maybe something to play around with on a lazy evening).
What inputs are you using to get that error?
Re: Using Stack Data Type to Solve an Infix Expression
That's excellent information to know. Thanks! I'll definitely take a look at the formatter.
But anyways, I'm just testing it out with a simple expression (8+8) ... and that doesn't work. It needs to handle all sort of infix (normal) expressions such as (5+5) + 6*3 + 11 ..
Re: Using Stack Data Type to Solve an Infix Expression
That's excellent information to know. Thanks! I'll definitely take a look at the formatter.
But anyways, I'm just testing it out with a simple expression (8+8) ... and that doesn't work. It needs to handle all sort of infix (normal) expressions such as (5+5) + 6*3 + 11 ..
Re: Using Stack Data Type to Solve an Infix Expression
***UPDATE***
I got it to work.. but not fully. I can enter an expression like 5 + 5 and it will work. ( 5 + 5 )... will not work. And if I enter an expression without spaces it will not work.
I get this error:
Exception in thread "main" java.util.EmptyStackException
at java.util.Stack.peek(Stack.java:85)
at java.util.Stack.pop(Stack.java:67)
at InfixEvaluation.evalz(InfixEvaluation.java:45)
at InfixConsole.main(InfixConsole.java:14)
