Full lesson preview

Evaluate an infix expression using stacks

Parse and evaluate an infix arithmetic expression with parentheses and +,-,*,/ using two stacks.

Python practice18 minStacks & QueuesIntermediateLast updated March 27, 2026

Problem statement

Given a string expression containing non-negative integers, the binary operators +, -, *, /, and parentheses '(',')', evaluate the expression and return the integer result. The expression may contain spaces. Use two stacks (values and operators) to parse and compute the expression without using eval(). Division should truncate toward zero (e.g., 3/2 -> 1, -3/2 -> -1).

Task

Implement a calculator that evaluates infix expressions with correct operator precedence and parentheses using stacks.

Examples

Expression with precedence

Input

"3+2*2"

Output

Multiplication before addition: 2*2=4, 3+4=7.

Input format

One string argument: the infix expression. Example: evaluate_infix("(1+2)*3")

Output format

An integer result of evaluating the expression.

Constraints

- The expression only contains non-negative integers, +, -, *, /, parentheses, and spaces. - You must not use Python's eval(). - Use O(n) time and O(n) space for the stacks.

Samples

Sample 1

Input

" (1+(4+5+2)-3)+(6+8) "

Output

Evaluate inner parentheses and apply operations in correct order.