Arithmetic Expression(Infix) Evaluation using Stack

Now that we already know how to implement a Stack in python, it's time to use it.

Here we will be writing a simple algorithm to solve a given arithmetic expression in infix form using Stack.

There are a few important points to note:

1. We will keep the program simple and will only evaluate expressions with +. -, * and / operators.
2. Parenthesis changes everything. It divides a simple linear expression into sections to be solved separately. So we will have to deal with opening and closing parenthesis carefully.
3. Operator precedence is another tricky factor here. Although it will be easier for us as we are writing the algorithm for only 4 operators, specified in point 1.
4. We will be using two stacks, one for operators and parenthesis, and the other one to store the numerical values.

Here is the algorithm for solving an arithmetic expression using Stacks.

1. We will start iterating the expression from left to right.
2. If we encounter an opening parenthesis (, we will push it in the operator stack.
3. If we encounter any numeric value, we have to push it in the values stack.
   • But, what if the number is a two digit or three digit number, we first have to form the complete number. So when we encounter a numeric value, we look for consecutive members of the expression, if we find another number, we append it to existing number.
   • We will do this, until we encounter token other than a number.
   • For example: If we have expression (22+2)*4, in this case our expression is made of following tokens ['(','2','2','+','2',')','*','4'], hence on encountering the first 2, we should look for consecutive tokens, if its a number, which in this case is, we append it to existing number to make it 22
4. If we encounter a closing parenthesis ), we pop an operator from the operator stack and two data elements from the value stack and apply the operator to the numeric values and store the result in the value stack.
5. If we encounter an operator, we will push it in the operator stack.
   • If operator stack is not empty and the operator present in the stack has higher precedence than the current operator, then we pop the operator with high precedence, and two values from the value stack, apply the operator to the values and store the result in the value stack.
   • And, push the current iterated operator in the operator stack.
6. Once we have iterated the entire expression, we pop one operator from the operator stack and two values from the value operator and apply the operator to the values, store the result in the value stack, and keep on repeating this, until we have just a single value left in the value stack.
7. The last value in the value stack will be the result.

Try changing the code as you like. Click the button, to Run the code again.