Infix Expression Evaluation (Two Stacks)
Evaluate infix expressions in O(n) using two stacks (operands and operators) with operator precedence and associativity. Supports parentheses and standard arithmetic.
Visualization
Interactive visualization for Infix Expression Evaluation (Two Stacks)
Use: A-Z, 0-9, +, -, *, /, ^, (, )
Interactive visualization with step-by-step execution
Implementation
1function evaluateInfix(expr: string): number {
2 const ops: string[] = [];
3 const vals: number[] = [];
4 const prec: Record<string, number> = { '+':1, '-':1, '*':2, '/':2, '^':3 };
5 const rightAssoc = new Set(['^']);
6 const tokens = expr.match(/d+.?d*|[()+-*/^]/g) || [];
7 const apply = () => {
8 const op = ops.pop();
9 if (!op) return;
10 const b = vals.pop()!; const a = vals.pop()!;
11 switch (op) {
12 case '+': vals.push(a + b); break;
13 case '-': vals.push(a - b); break;
14 case '*': vals.push(a * b); break;
15 case '/': vals.push(Math.trunc(a / b)); break; // define trunc toward 0
16 case '^': vals.push(Math.pow(a, b)); break;
17 }
18 };
19 for (const t of tokens) {
20 if (/^d/.test(t)) { vals.push(parseFloat(t)); continue; }
21 if (t === '(') { ops.push(t); continue; }
22 if (t === ')') {
23 while (ops.length && ops[ops.length - 1] !== '(') apply();
24 ops.pop();
25 continue;
26 }
27 while (
28 ops.length && ops[ops.length - 1] !== '('
29 && (
30 prec[ops[ops.length - 1]] > prec[t]
31 || (prec[ops[ops.length - 1]] === prec[t] && !rightAssoc.has(t))
32 )
33 ) apply();
34 ops.push(t);
35 }
36 while (ops.length) apply();
37 return vals.pop() ?? 0;
38}Deep Dive
Theoretical Foundation
Scan tokens left-to-right maintaining two stacks: values and ops. On number ⇒ push to values. On '(' ⇒ push to ops. On ')' ⇒ apply ops until '(' is found. On operator ⇒ apply while top op has greater precedence (or equal and left-associative). Finally apply remaining ops. Equivalent to Dijkstra's two-stack algorithm and closely related to the shunting-yard algorithm.
Complexity
Time
O(n)
O(n)
O(n)
Space
O(n)
Applications
Industry Use
Calculator applications
Programming language interpreters
Spreadsheet expression engines
Scripting and DSL evaluators
Educational tools for parsing/evaluation
REPLs and interactive math tools
Use Cases
Related Algorithms
Binary Search Tree (BST)
A hierarchical data structure where each node has at most two children, maintaining the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This ordering property enables efficient O(log n) operations on average for search, insert, and delete. BSTs form the foundation for many advanced tree structures and are fundamental in computer science.
Stack
LIFO (Last-In-First-Out) data structure with O(1) push/pop operations. Stack is a fundamental linear data structure where elements are added and removed from the same end (top). It's essential for function calls, expression evaluation, backtracking algorithms, and undo operations in applications.
Queue
FIFO (First-In-First-Out) data structure with O(1) enqueue/dequeue operations. Queue is a fundamental linear data structure where elements are added at one end (rear) and removed from the other end (front). Essential for breadth-first search, task scheduling, and buffering systems.
Hash Table (Hash Map)
A data structure that implements an associative array abstract data type, mapping keys to values using a hash function. Hash tables provide O(1) average-case time complexity for insertions, deletions, and lookups, making them one of the most efficient data structures for key-value storage. The hash function computes an index into an array of buckets from which the desired value can be found.