Algorithm to evaluate an infix expression

A infix expression is a mathematical expression in which the operator comes between the operands. For example, 2 + 3 means 2 plus 3. Infix expressions often use parentheses to show the order of operations, especially when there are multiple operators.

To evaluate an infix expression, we follow the operator precedence rules (like multiplication/division before addition/subtraction) and solve expressions inside parentheses first. This method is how we normally calculate math problems, but for computers, evaluating infix expressions directly is a bit more complex because they must track precedence and parentheses.

What is infix expression ?

An infix expression is a way of writing mathematical expressions where the operator is placed between two operands. This is the most common and natural way humans write equations. For example, in the expression A + B, the operator ‘+’ is written between the operands A and B. Other examples include A + B * C or (A + B) – C.

Infix expressions are easy for people to read and understand, but they are harder for computers to evaluate directly because of the need to follow rules like operator precedence (which operator to perform first) and parentheses. For example, in A + B * C, multiplication is done before addition because of operator precedence. Therefore, infix expressions are often converted into other forms like postfix or prefix for easier computation by computers.

Point to consider

1. Permitted operands: A, B, C, D means any real number is permitted.
2. Permitted operators: +,-, *, /, ^(exponentiation)
3. Blanks are permitted in the expression
4. Parenthesis are permitted

Suppose given infix expression is

A+B*C-D

where A,B,C,D are operands and +,*,- are operators.

To solve the above infix expression we will use two stack

Operand Stack : This stack will hold operands.

Operator Stack : This stack will hold operators.

Algorithm to evaluate infix expression

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

1. If the character is an operand, push it onto the operand stack.
2. If the character is “(“, then push it onto the operator stack.
3. If the character is “)”, then “process” as explained above until the corresponding “(” is encountered in the operator stack. At this stage POP the operator stack and ignore “(.”
4. If we encounter an operator
   • If the operator stack is empty then push the operator onto the operator stack.
   • If the operator stack is not empty and the operator’s precedence is greater than the precedence of the stack top of the operator stack, then push the character onto the operator stack.
   • If the operator stack is not empty and the character’s precedence is lower than the precedence of the stack top of operator stack 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.
5. 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.
6. The last value in the value stack will be the result.

Example for postfix expression

Expression: (2 + 3) * 4 – 5

We will evaluate it using a stack.

Step 1: Follow Parentheses First

• Infix expressions respect parentheses.
• Inside parentheses: (2 + 3) → 2 + 3 = 5
• Expression becomes:

5 * 4 - 5

Step 2: Follow Operator Precedence

• Multiplication and division have higher precedence than addition and subtraction.
• Perform 5 * 4 = 20
• Expression becomes:

20 - 5

Step 3: Perform Remaining Operations

• Perform subtraction: 20 - 5 = 15

Step 4: Final Result

• Result of (2 + 3) * 4 - 5 is 15