🙏

জয়  শ্রী  রাম

🕉

---

There are three ways of writing an expression: Infix, Prefix, Postfix. Computers evaluate expressions in Prefix or Postfix, whereas humans are more familiar and comfortable with Infix way of denoting an expression.
The order of operations within prefix and postfix expressions is completely determined by the position of the operator and nothing else. But this is not the case for Infix, and this is what makes evaluating an Infix expression tricky.

So let's talk about Infix expression in this chapter, and we will dive deeper in Prefix and Postfix expression in the next chapter.

Before going to discuss the algorithm of how to evaluate an Infix expression let's think about how humans evaluate a numerical expression with non-negative numbers. The purpose of this is to discuss my thought process to reach at the algorithm.

Many of us might have heard about the term BODMAS in Arithmetic and Algebra classes while in school, which states that the order in which the operators should be processed in an expression. In BODMAS : B = Braces, O = of, D = Division, M = Multiplication, A = Addition, S = Subtraction. What it states is

1. The parts of the expression surrounded by opening brace and closing brace must be calculated first.
2. Next, operator 'of' should be processed.
3. Next process division and multiplication. If '/' and '*' are next to each other (like 16 * 2 / 8) then process them from left to right. 16 * 2 / 8 = 4.
4. Next comes Addition and Subtraction. Again if '+' and '-' are next to each other, process them from left to right.

The whole BODMAS thing brings in the concept of Precedence which will govern much of the algorithm we are going to devise. Precedence governs which operator has relatively more priority. Operators with more priority are processed first.
Order of Precedence / Priority:
'^' > '/' = '*' > '+' = '-'

From the discussion above we note few things:

As we scan the expression from left to right:

• Since we process from left to right, whenever we get an operator that has precedence less than or equal to the preceding operator, then evaluate the processed part of the expression before processing this operator. Let's look at these expressions:
  
  • 8 / 2 + 1
    When we are processing the operator '+', we see that the preceding operator '/' has precedence greater than the operator we are trying to process, sine Precedence of '/' > Precedence of '+'. So we should evaluate the part of the expression that is on the left of the operator '+', before we process the operator '+'.
    8 / 2 + 1 = (8 / 2) + 1
  • 8 - 2 + 1
    When we are processing the operator '+', we see that the preceding operator '-' has precedence equal to the operator we are trying to process, sine Precedence of '-' is equal to the Precedence of '+'. So we should evaluate the part of the expression that is on the left of the operator '+', before we process the operator '+'.
    8 - 2 + 1 = (8 - 2) + 1
• Since parts of expression surrounded by braces need to be evaluated first, when we find a closing brace ')', we should complete evaluation the part of expression in between '(' and ')'.

Algorithm to evaluate an Infix Expression involving non-negative operands:

1. Have two stack, one for storing operators, and another one for storing operands.
2. Iterate over the expression from left to right.
3. While iterating over the expression if you encounter anything other than valid operands and operators (including opening brace and closing brace), ignore them. This step does not apply if the expression is already sanitized to make sure the expression is valid and only valid characters exists in the expression.
4. While iterating, if you get an operand, just push it in the operand stack.
5. While iterating over the expression, if you encounter an operator (say, op1):
   • if the operator stack is empty or if the precedence of the operator (op1) is greater than the operator on the top of the operator stack, then just push the operator in the operator stack.
   • it gets interesting if the operator we encounter has a precedence less than or equal to the precedence of the operator that is at the top of the operator stack.
     In this case, we need to evaluate the expression first, starting from the last operand encountered, in backward, till we either find a opening brace '(' or an operator which has precedence lower than or equal to the operator op1. To achieve this we need to follow the below three steps.
     
     • Pop top two operands from the operands stack and pop the top operator from the operator stack and process them, by process I mean calculate the value you get by operating the operator on the two operands. For example, if the first popped operand is 3 and the second popped operand is 6 and the operator is '/', then do the operation <second popped operand> <ltoperator> <second popped operand>. In our case it would be 6 / 3
     • Now push the value you got in the above step in the operands stack. In our case push 2 in the operands stack. We got 2 from the operation 6 / 3.
     • Repeat the above 2 steps, till we encounter opening brace '(' or an operator with precedence equal to less than the operator op1.
     It is important to note, why we are doing the above two steps even when the precedence is same. The short answer is because of ASSOCIATIVITY.
     Consider the expression 6 - 3 - 2.
     This expression can have two answers (of course, one of them is not correct) depending on how we calculate it.
     We get the calculated value as 5 if we calculate the expression in the following way: 6 - (3 - 2). But is this correct? No.
     We get the correct answer if we calculate 6 - 3 - 2 as (6 - 3) - 2 and we get 1.
     
     So what we can conclude here is we need to process (calculate) from left to right if the precedence of the operators are the same.
     
     A little more on this: Addition (+) and Multiplication (*) operators are Associative. If an expression has all associative operators with same precedence, it does not matter in which order you process them you will get the same answer.
     3 + 4 + 5 = (3 + 4) + 5 = 3 + (4 + 5) = 12
     3 * 4 * 5 = (3 * 4) * 5 = 3 * (4 * 5) = 60.
     
     
     
     
6. Now that we have visited all the characters in the expression and put them in the stack and done any operations necessary, we need to process the operands and operators present in the two stack.
   
   
   Important to notice that: for whatever we have left in the two stacks now, NON-ASSOCIATIVITY does not matter right now, what I mean by this you would get same calculated value irrespective of you process the left-over expression we have right now from left to right or right to left.
   
   
   To do this,
   • Pop the top two operands and pop the operators stack, process and put the result in the operands stack.
   • Repeat till the operators stack is empty.

Java:

// throws exception if divide by zero is attempted
public int evaluateInfixExpression(String expression) throws Exception {

    Deque<Integer> operands = new ArrayDeque<>();
    Deque<Character> operators = new ArrayDeque<>();

    char[] ch = expression.toCharArray();

    for(int i = 0; i < ch.length; i++) {
        char c = ch[i];

        if(Character.isDigit(c)){
            //operands can be one or more digits long
            int num = 0;
            while (i < ch.length && Character.isDigit(ch[i])) {
                num = num * 10 + (ch[i] - '0');
                i++;
            }
            i--;
            operands.push(num);
        }
        else if( c == '('){
            operators.push(c);
        }
        else if(c == ')') {
            // calculate the whole expression surrounded by the closing and corresponding braces
            while(operators.peek() != '('){
                int ans = calculate(operands, operators);
                operands.push(ans);
            }
            operators.pop();
        }
        else if(isOperator(c)){
            while(!operators.isEmpty() && precedence(c) <= precedence(operators.peek())){
                int ans = calculate(operands, operators);
                operands.push(ans);
            }
            operators.push(c);
        }
    }

    // all the characters in the expression have been visited and put on the stack
    // with some operations done whenever necessary.
    // Now just calculate everything you have in stack
    while(!operators.isEmpty()){
        int ans = calculate(operands, operators);
        operands.push(ans);
    }
    return operands.pop();
}

private boolean isOperator(char c) {
    return (c=='+'||c=='-'||c=='/'||c=='*'||c=='^');
}

private int precedence(char c) {
    switch (c){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '^':
            return 3;
    }
    return -1;
}

private int calculate(Deque<Integer> operands, Deque<Character> operators) throws Exception {

    int a = operands.pop();
    int b = operands.pop();

    char operator = operators.pop();

    switch (operator) {
        case '+':
            return a + b;
        case '-':
            return b - a; // not a - b since evaluation is done from left to right.
        case '*':
            return a * b;
        case '^':
            return  (int) Math.pow(b, a);
        case '/':
            if (a == 0) {
                throw new Exception("Cannot divide by zero");
            }
            return b / a; // not a / b since evaluation is done from left to right.
    }
    return 0;
}

Python:

def evaluateInfixExpression(self, expression):
    operands = ArrayDeque()
    operators = ArrayDeque()
    ch = expression.toCharArray()
    i = 0
    while i < len(ch):
        c = ch[i]
        if c.isdigit():
            num = 0
            while i < len(ch) and (ch[i]).isdigit():
                num = num * 10 + (ch[i] - '0')
                i += 1
            i -= 1
            operands.push(num)
        elif c == '(':
            operators.push(c)
        elif c == ')':
            while operators.peek() != '(':
                ans = self._calculate(operands, operators)
                operands.push(ans)
            operators.pop()
        elif self._isOperator(c):
            while (not operators.isEmpty()) and self._precedence(c) <= self._precedence(operators.peek()):
                ans = self._calculate(operands, operators)
                operands.push(ans)
            operators.push(c)
        i += 1
    while not operators.isEmpty():
        ans = self._calculate(operands, operators)
        operands.push(ans)
    return operands.pop()
def _isOperator(self, c):
    return (c=='+' or c=='-' or c=='/' or c=='*' or c=='^')
def _precedence(self, c):
    if (c == '+') or (c == '-'):
        return 1
    if (c == '+') or (c == '-') or (c == '*') or (c == '/'):
        return 2
    if (c == '+') or (c == '-') or (c == '*') or (c == '/') or (c == '^'):
        return 3
    return -1

def _calculate(self, operands, operators):
    a = operands.pop()
    b = operands.pop()
    operator = operators.pop()
    if operator == '+':
        return a + b
    if (operator == '+') or (operator == '-'):
        return b - a # not a - b since evaluation is done from left to
    if (operator == '+') or (operator == '-') or (operator == '^'):
        return int(b ** a)
    if (operator == '+') or (operator == '-') or (operator == '^') or (operator == '/'):
        if a == 0:
            raise Exception("Cannot divide by zero")
        return round(b / float(a))
    return 0