How to evaluate an infix expression in just one scan using stacks?

Question

I want to know if there is a way to solve infix expressions in a single pass using 2 stacks? The stacks can be one for operator and the other for operands...

The standard way to solve by shunt-yard algorithm is to convert the infix expression to postfix(reverse polish) and then solve. I don't want to convert the expression first to postfix.

If the expression is like 2*3-(6+5)+8, how to solve?

Imprescriptible

Answer 1

Quite late, but here is the answer.

Take two stacks:

1. operator stack { for operators and parentheses }.
2. operand stack.

Algorithm

If character exists to be read:

1. If character is operand push on the operand stack, if character is (, push on the operator stack.
2. Else if character is operator
   1. While the top of the operator stack is not of smaller precedence than this character.
   2. Pop operator from operator stack.
   3. Pop two operands (op1 and op2) from operand stack.
   4. Store op1 op op2 on the operand stack back to 2.1.
3. Else if character is ), do the same as 2.2 - 2.4 till you encounter (.

Else (no more character left to read):

• Pop operators untill operator stack is not empty.
• Pop top 2 operands and push op1 op op2 on the operand stack.

return the top value from operand stack.

Trihedral

"[do the same as 2 till you encounter )" - there should be '(' instead of ')' I believe! (this typo in my algorithm caused some headaches!!) – Moline

@EJP never heard of any Shunting-yard Algorithm. I came up with this algorithm myself and it can be a case that dijkstra came up with this even before me. I would have done that otherwise.. Instead of asking me first and giving it a -1 only after confirmation with me, I challange you to proove that I could not have come up with this algorithm all by myself and this text is adapted or copied from somewhere. I would be happy to do the necessary changes in that case. thanks – Trihedral

Wow, giving a -1 for that is beyond obnoxious. – Firing

Very important portion of the algorithm to work is as @Moline said " if input is a ): 1 While the thing on top of the operator stack is not a (: " – Fearsome

@EJP Djikstra is a great scientist, but I do think students can come up with this algorithm, especially given the clue to use two stacks. – Thurlough

@Rohit: looks like you have an error (typo) "if character is operand or (. push on the operandStack". '(' should be pushed to the operator stack, not operandStack. – Thurlough

After 2 stack clue students can definitely write this today(Time is important part) – Fend

for any interested folk, step 1 should be "1. if character is operand or (. push to the Stack: if operand push on the operandStack and if ( on the operatorStack." – Sheers

i am not -1 because its the same as Djisktra, im -1 because it doesn't work. There is nowhere in this algorithm that pushes an operator onto the operator stack, which is fundamental to it working. This should not be the accepted answer and these upvotes are all wrong. – Marva

Correction: "store/push op2 op op1 on the operand stack" rather than "store/push op1 op op2 on the operand stack". This order would matter for operators like exponent etc. – Tutty

if infix expression is invalid, like 7*+8, *9+, 7/(32+9, how to judge it? – Bream

Answer 2

The method given in the link is really good.

Let me quote the source:

We will use two stacks:

Operand stack: to keep values (numbers)  and

Operator stack: to keep operators (+, -, *, . and ^).  


In the following, “process” means, (i) pop operand stack once (value1) (ii) pop operator stack once (operator) (iii) pop operand stack again (value2) (iv) compute value1 operator  value2 (v) push the value obtained in operand stack.          


Algorithm:


Until the end of the expression is reached, get one character and perform only one of the steps (a) through (f):

(a) If the character is an operand, push it onto the operand stack.

(b) If the character is an operator, and the operator stack is empty then push it onto the operator stack.

(c) If the character is an operator and the operator stack is not empty, and the character's precedence is greater than the precedence of the stack top of operator stack, then push the character onto the operator stack.

(d) If the character is "(", then push it onto operator stack.

(e) If the character is ")", then "process" as explained above until the corresponding "(" is encountered in operator stack.  At this stage POP the operator stack and ignore "(."

(f) If cases (a), (b), (c), (d) and (e) do not apply, then process as explained above.



 When there are no more input characters, keep processing until the operator stack becomes empty.  The values left in the operand stack is the final result of the expression.

I hope this helps!

Litter

Good, except in the "process" step the order of the operands is swapped -- you pop operand2 first, then operand1, then comput operand1 operator operand2... – Llovera

Answer 3

1. create an empty operator stack.
2. create an empty operand stack.
3. for each token in the input String
   a. get the next token in the infix string.
   b. if the next is an operand, place it on the operand stack.
   c. if the next token is an operator
   • Evaluate the operator.
4. while operator stack is not empty, pop operator and operands (left and right),evaluate left operator right and push result onto operand stack.
5. pop result from operator stack.

Periphrastic

No mention of operator precedence here. – Crowberry

Answer 4

Below is my attempt at infix expression evaluation in java. Please let me know if you find any bugs :)

import java.util.*;

public class ArithmeticExpressionEvaluation {

    public static void main(String[] args) {
        Scanner readExpression = new Scanner(System.in);
        System.out.print("Enter the expression: ");
        String expression = readExpression.nextLine();
        System.out.println(expression);
        System.out.println("Result: " + calculateExpression(expression));
    }

    public static long calculateExpression(String expression) {

        Stack<Long> operandStack = new Stack<>();
        Stack<Character> operatorStack = new Stack<>();

        if (!isValidExpression(expression)) {
            System.out.println("Not a valid expression to evaluate");
            return 0;
        }

        int i = 0;
        String currentInteger = null;
        while (i < expression.length()) {

            // System.out.println(expression.charAt(i));
            if (expression.charAt(i) >= '0' && expression.charAt(i) <= '9') {

                currentInteger = expression.charAt(i) + "";
                i++;
                while (i != expression.length() && (expression.charAt(i) >= '0' && expression.charAt(i) <= '9')) {
                    currentInteger = currentInteger + expression.charAt(i);
                    i++;
                }

                operandStack.push(Long.parseLong(currentInteger));
            } else {

                if (expression.charAt(i) == ')') {

                    while (operatorStack.peek() != '(') {
                        performArithmeticOperation(operandStack, operatorStack);
                    }
                    operatorStack.pop();
                } else {

                    Character currentOperator = expression.charAt(i);
                    Character lastOperator = (operatorStack.isEmpty() ? null : operatorStack.peek());


                    if (lastOperator != null && checkPrecedence(currentOperator, lastOperator)) {
                        performArithmeticOperation(operandStack, operatorStack);
                    }
                    operatorStack.push(expression.charAt(i));

                }
                i++;
            }

        }


        while (!operatorStack.isEmpty()) {
            performArithmeticOperation(operandStack, operatorStack);
        }

    //    System.out.println(Arrays.toString(operandStack.toArray()));
    //    System.out.println(Arrays.toString(operatorStack.toArray()));

        return operandStack.pop();

    }

    public static void performArithmeticOperation(Stack<Long> operandStack, Stack<Character> operatorStack) {
        try {
            long value1 = operandStack.pop();
            long value2 = operandStack.pop();
            char operator = operatorStack.pop();

            long intermediateResult = arithmeticOperation(value1, value2, operator);
            operandStack.push(intermediateResult);
        } catch (EmptyStackException e) {
            System.out.println("Not a valid expression to evaluate");
            throw e;
        }
    }


    public static boolean checkPrecedence(Character operator1, Character operator2) {

        List<Character> precedenceList = new ArrayList<>();
        precedenceList.add('(');
        precedenceList.add(')');
        precedenceList.add('/');
        precedenceList.add('*');
        precedenceList.add('%');
        precedenceList.add('+');
        precedenceList.add('-');


        if(operator2 == '(' ){
            return false;
        }

        if (precedenceList.indexOf(operator1) > precedenceList.indexOf(operator2)) {
            return true;
        } else {
            return false;
        }

    }

    public static long arithmeticOperation(long value2, long value1, Character operator) {

        long result;

        switch (operator) {

            case '+':
                result = value1 + value2;
                break;

            case '-':
                result = value1 - value2;
                break;

            case '*':
                result = value1 * value2;
                break;

            case '/':
                result = value1 / value2;
                break;

            case '%':
                result = value1 % value2;
                break;

            default:
                result = value1 + value2;


        }
        return result;
    }


    public static boolean isValidExpression(String expression) {

        if ((!Character.isDigit(expression.charAt(0)) && !(expression.charAt(0) == '('))
                || (!Character.isDigit(expression.charAt(expression.length() - 1)) && !(expression.charAt(expression.length() - 1) == ')'))) {
            return false;
        }

        HashSet<Character> validCharactersSet = new HashSet<>();
        validCharactersSet.add('*');
        validCharactersSet.add('+');
        validCharactersSet.add('-');
        validCharactersSet.add('/');
        validCharactersSet.add('%');
        validCharactersSet.add('(');
        validCharactersSet.add(')');

        Stack<Character> validParenthesisCheck = new Stack<>();

        for (int i = 0; i < expression.length(); i++) {

            if (!Character.isDigit(expression.charAt(i)) && !validCharactersSet.contains(expression.charAt(i))) {
                return false;
            }

            if (expression.charAt(i) == '(') {
                validParenthesisCheck.push(expression.charAt(i));
            }

            if (expression.charAt(i) == ')') {

                if (validParenthesisCheck.isEmpty()) {
                    return false;
                }
                validParenthesisCheck.pop();
            }
        }

        if (validParenthesisCheck.isEmpty()) {
            return true;
        } else {
            return false;
        }
    }
}

Eugenle

2+3(4*3) is giving me output as 15. check once – Custer

Answer 5

---- This is for expressions without parentheses ----

Only works for basic expressions with 2 operators

1. Create an empty Operator Stack

2. Create an empty Operand Stack

3. Create a character array from string expression

4. For each character

   4.1 If it is a digit

   • Add it to the Operand Stack

   4.2 If it is an operator

   • While the Operator Stack is empty and the current operator is of less precedence than the top operator from the Operator Stack

     {

   • Pop one operand (v1)

   • Pop a second operand (v2)

   • Pop an operator (p)

   • Evaluate v2 p v1 (First number that was pushed on will be last to be popped)

   • Push result onto Operand Stack

     }

   • In case of empty Operator Stack simply add the operator to the stack

5. After reading through each character

   5.1 While the Operator Stack is not empty

   • Same process as described in 4.2 while loop
   • Return final result

Fadeout

Answer 6

If you want to handle both unary and binary operators as well as detecting all possible errors, the following is an overview of the Double-E approach to parsing infix expressions:

• Create an empty Operand Stack — note that if parsing for AST then this is a stack of ASTs.

• Create an empty Operator Stack — note that the operator enum represents true operators in the language being parsed, not tokens (so, operators here are not simply "+" but differentiated as unary + vs. binary +).

• Start in Unary State.

---

• Unary State:
  • if you find an operand, push that on the Operand Stack and switch to Binary State.
  • if you find an operator, say +, then it is unary +, so push unary + onto the Operator Stack and stay in Unary State
  • if you find an open paren (, then push grouping paren onto the Operator Stack, stay in Unary State
  • if you find end-of-input, then error, incomplete parse
• Binary State
  • if you find end of input, then Exit State
  • if you find an operand, this is juxtaposition, which is an error in most languages, but you can do something useful if desired.
  • if you find an operator, say +, then it is a binary +, so Reduce, then push binary + onto the Operator Stack and switch to Unary State.
  • if you find a close paren ), then Reduce until matching ) (which could be a function call Operator or grouping paren Operator), stay in Binary State
• Exit State
  • Reduce all operators on the Operator Stack by taking their operands off of the Operand Stack
  • when finished, should have no operators on Operator Stack, and exactly one operand on the Operand Stack, and that one operand is the answer to the parse.

Differentiation between unary and binary state allows for the industrial strength of this approach, and without that the knowledge of which state, many things cannot be differentiated, and/or error conditions detected.

Reduction, when called for, and which happens for a number of different reasons, is a matter of assembling recognized piece parts into a larger whole.  In essence, pulling an operator off of the Operator Stack, and as many operands as that operator takes off of the Operand Stack, assembling those into a recognized unit, such as with an AST fragment, and pushing that onto the Operand Stack.  Reduction continues until some limit is reached such as empty Operand Stack (used in End State), or the precedence of the current operator is higher than that of the operator on the top of the Operator Stack.

A more formal writeup can be found here.

This approach can handle unary operators, binary operators, pre/post fix unary, grouping parenthesis, functions & function invocation, array references, casts, etc..  This approach is industrial strength (i.e. without the many short comings in Shunting Yard, for example).

Component