Infix expressions evaluated in DSA?

What is an Infix Expression?

• An infix expression is the standard way we write math: operators are placed between operands.
  Example: A + B * C

The challenge: You can’t just evaluate left to right because multiplication/division have higher precedence than addition/subtraction.

How to Evaluate Infix Expressions

There are two main approaches:

1. Convert Infix ? Postfix (or Prefix) and Evaluate

• Use the Shunting Yard Algorithm (by Dijkstra) to convert infix to postfix.

• Then evaluate the postfix expression using a stack.

Steps:

1. Scan the infix expression left to right.

2. Use a stack to store operators and parentheses.

3. Apply precedence and associativity rules to reorder operators.

4. Generate a postfix expression.

5. Evaluate postfix using another stack (push operands, pop two when operator appears, apply operator, push result).

Example:

Infix:   3 + 4 * 2
Postfix: 3 4 2 * +
Evaluate: 3 + (4*2) = 11

2. Direct Evaluation Using Two Stacks

• Maintain two stacks:

  • Operand stack (numbers)

  • Operator stack (+, -, *, /, etc.)

• Algorithm:

  1. Scan the infix expression left to right.

  2. Push operands onto the operand stack.

  3. Push operators onto the operator stack, but handle precedence:

     • If the new operator has lower/equal precedence than the top of the stack, pop and evaluate first.

  4. Handle parentheses by pushing ( and popping until you find it.

  5. At the end, apply remaining operators.

Example:

Expression: (3 + 4) * 2
Operand stack: [3, 4, 2]
Operator stack: [+, *]
Evaluation: (3+4)=7 ? 7*2=14

Comparison of Approaches

In Practice

• Postfix conversion + evaluation is the most common in DSA courses and competitive programming because it’s easier to implement and debug.

• Direct two-stack evaluation is closer to how compilers/interpreters work internally.

To evaluate infix expressions, we generally follow a two-step process: conversion to postfix notation (also known as Reverse Polish Notation) and then evaluation of the postfix expression.

1. Conversion to Postfix: This can be achieved using the Shunting Yard algorithm developed by Edsger Dijkstra. The algorithm utilizes a stack to hold operators and ensures that the output maintains the correct order of operations (precedence and associativity).

   def infix_to_postfix(expression):
       precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
       output = []
       stack = []
       
       for char in expression:
           if char.isalnum():  # If the character is an operand
               output.append(char)
           elif char in precedence:  # If the character is an operator
               while (stack and stack[-1] != '(' and
                      precedence[char] <= precedence[stack[-1]]):
                   output.append(stack.pop())
               stack.append(char)
           elif char == '(':
               stack.append(char)
           elif char == ')':
               while stack and stack[-1] != '(':
                   output.append(stack.pop())
               stack.pop()  # Remove '(' from stack
       
       while stack:
           output.append(stack.pop())
       
       return ''.join(output)
   

2. Evaluation of Postfix: Once we have the postfix expression, we can evaluate it using another stack. Each operand is pushed onto the stack, and when an operator is encountered, the required number of operands is popped from the stack, the operation is performed, and the result is pushed back onto the stack.

   def evaluate_postfix(expression):
       stack = []
       for char in expression:
           if char.isdigit():  # If the character is an operand
               stack.append(int(char))
           else:  # The character is an operator
               b = stack.pop()
               a = stack.pop()
               if char == '+':
                   stack.append(a + b)
               elif char == '-':
                   stack.append(a - b)
               elif char == '*':
                   stack.append(a * b)
               elif char == '/':
                   stack.append(a / b)
       return stack[0]