Using two stacks to evaluate an infix expression

Question

I have to create two stacks and evaluate an infix expression like 3 + 4 + ( 5 -2 ). I have created a code doing it with postfix to create the base since it is easier and it works flawlessly! Now the problem I have is with the parenthesis, I do not know how to check for the parenthesis to be balanced and then if they are evaluate the expression correctly. It should be something like:

Type a balanced infix expression: 5 * (4 + 3)
The result is 35
Type a balanced infix expression: 10 / (2 + 1
Not balanced, try again :

Here is the tester

import java.util.*;
public class InfixTester { //it's postfix at the moment
    public static void main(String[] args) {
        String expression, retry;
        int result;

        Scanner scan = new Scanner (System.in);

        do {
            InfixEvaluator evaluator = new InfixEvaluator(); //in reality is postfix rn
                System.out.println ("Type a balanced postfix expression one token at a time:");
                expression = scan.nextLine();

                result = evaluator.evaluate(expression);
                System.out.println();
                System.err.println("The result is " + result);

                System.out.print("Would you like to continue (y/n)? ");
                retry = scan.nextLine();
                System.out.println();
        }
        while (retry.equalsIgnoreCase("y"));
    }
}

And here is the evaluator where everything is

import java.util.*;
public class InfixEvaluator {  //it's actually postfix right now
    private final static char ADD = '+';
    private final static char SUBSTRACT =  '-';
    private final static char MULTIPLY = '*';
    private final static char DIVIDE = '/';

    private Stack <Integer> stack;
    public InfixEvaluator() {
        stack = new Stack <Integer>();
    }

    public int evaluate(String expr) {
        int op1, op2, result = 0;
        String token;
        Scanner parser = new Scanner (expr);

        while (parser.hasNext()) {
            token = parser.next();

            if (isOperator (token)) {
                op2 = (stack.pop()).intValue();
                op1 = (stack.pop()).intValue();
                result = evaluateSingleOperator(token.charAt(0), op1, op2);
                stack.push(new Integer (result));
            }
            else
                stack.push(new Integer (Integer.parseInt (token)));
        }
        return result;
    }

    private boolean isOperator (String token){
        return ( token.equals("+") || token.equals("-") ||
                token.equals("*") || token.equals("/"));
    }

    private int evaluateSingleOperator(char operation, int op1, int op2){
        int result = 0;

        switch  (operation){
            case ADD:
                result = op1 + op2;
                break;
            case SUBSTRACT:
                result = op1 - op2;
                break;
            case MULTIPLY:
                result = op1 * op2;
                break;
            case DIVIDE:
                result = op1 / op2;
                break;                                
        }
        return result;
    }
}

While all this works just fine for postfix expressions, what do I need to change and add in order to evaluate correctly infix expressions instead? Thanks!

Best thing would be to take in an infix expression and create a method that will convert that expression to postfix. You can do it using stacks also. As for parenthesis, keep a count; when you find an opening bracket add to the count, when you find a closing brakcet subtract from the count. If the count is 0 when at the end then the parenthesis are balanced. — this_is_cat, Feb 22 '19 at 20:55
You might find this [answer](https://stackoverflow.com/questions/13421424/how-to-evaluate-an-infix-expression-in-just-one-scan-using-stacks) useful — StaticBeagle, Feb 22 '19 at 22:01

score 1 · Answer 1 · answered Feb 23 '19 at 00:36

I assume that the two stacks are for operators and for intermediate results. You can push the open paren to your operator stack. When you encounter a close paren, pop the stack and check if it is an open paren. If it is, you don't need to do anything. The top of the "intermediate results" stack is the value of the parenthesized expression. If the top of the stack was not an open paren, evaluate the operator as you normally would.

Using two stacks to evaluate an infix expression

1 Answers1