Infix expressions evaluated in DSA?

Question

How can we evaluate infix expressions in Data Structures and Algorithms (DSA)?

Jayraj Chhaya · Answer

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

Sandhiya Priya · Answer

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: Scan the infix expression left to right. Use a stack to store operators and parentheses. Apply precedence and associativity rules to reorder operators. Generate a postfix expression. 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: Scan the infix expression left to right. Push operands onto the operand stack. 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. Handle parentheses by pushing ( and popping until you find it. 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 Approach Pros Cons Convert to Postfix & Evaluate Simple, well-structured, widely used Requires two steps (conversion + eval) Direct Evaluation with Two Stacks No conversion step, evaluates inline More complex to implement correctly 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.

Infix expressions evaluated in DSA?

Insert Link

Embed YouTube Video

Table Options

Insert Image

Answers (2)