52

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?

5 Answers 5

85

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.

11
  • 2
    "[do the same as 2 till you encounter )" - there should be '(' instead of ')' I believe! (this typo in my algorithm caused some headaches!!)
    – Gyfis
    Jan 20, 2014 at 17:03
  • 31
    @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
    – Rohit
    Oct 14, 2014 at 22:44
  • 25
    Wow, giving a -1 for that is beyond obnoxious. Jun 12, 2015 at 3:32
  • 6
    @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. Feb 10, 2016 at 23:44
  • 2
    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." Aug 19, 2016 at 18:40
4

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!

1
  • Good, except in the "process" step the order of the operands is swapped -- you pop operand2 first, then operand1, then comput operand1 operator operand2...
    – Chris Dodd
    Aug 22, 2019 at 14:03
1
  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.
1
  • 7
    No mention of operator precedence here.
    – user207421
    Oct 29, 2015 at 10:09
1

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;
        }
    }
}
1
  • 2+3(4*3) is giving me output as 15. check once
    – Stunner
    Jun 2, 2020 at 15:40
0

---- 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.