Overview
Dijkstra's two-stack algorithm scans expression tokens, pushing values and operators until a closing parenthesis triggers one pending operation. The basic form assumes full parenthesization to avoid precedence decisions.
CoreSource checked
Dijkstra's Two-Stack Algorithm
Evaluates fully parenthesized expressions with separate stacks for operators and values.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Parsing
- Difficulty
- Beginner
- Family
- Expression Evaluation
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 2
- Code example
- Ready
- Visualization
- Ready
- Aliases
- Two-Stack Expression Evaluation
Core Concepts
parse stateoperator precedencestack stateexpression evaluationtoken streamgrammar rule
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)
When to Use
- Use when expressions are fully parenthesized and only a small operator set is needed.
- Use as a clear educational baseline before adding precedence tables.
When Not to Use
- Avoid for general expression grammars without adding precedence and associativity handling.
- Avoid when robust parser errors or language-level syntax recovery are required.
What It Does
- Pushes numbers onto a value stack
- Pushes operators onto an operator stack
- Evaluates one subexpression when a closing parenthesis appears
Use Cases
- Teaching stack-based expression evaluation
- Simple calculators for fully parenthesized expressions
- Introducing operator and operand stack invariants
Inputs
- Fully parenthesized expression tokens
Outputs
- Expression value
Key Formulas (1)
Operator application
value = apply(operator, leftvalue, rightvalue)
value = apply(operator, left_value, right_value)Reduces a parenthesized expression when a closing parenthesis is reached.
Pseudocode
- 1.For each token
- 2.If token is a number, push it on the value stack
- 3.If token is an operator, push it on the operator stack
- 4.If token is a closing parenthesis, pop one operator and its operands
- 5.Apply the operator and push the result
- 6.Return the final value
Canonical Example
- Input
- tokens = ['(', '2', '+', '(', '3', '*', '4', ')', ')']
- Output
- 14
- Explanation
- The inner multiplication is evaluated at its closing parenthesis, then the outer addition is evaluated.
Implementation Notes
- Tokenize before evaluation so numbers, operators, and parentheses are unambiguous.
- Check stack sizes before applying each operator.
- Test nested expressions and malformed parentheses.
Common Pitfalls
- The basic algorithm does not parse unparenthesized precedence such as 2 + 3 * 4.
- Stack underflow usually means malformed input and should be reported clearly.
- Unary operators need explicit handling rather than being treated as binary operators.
Interactive Mechanism Walkthrough
Sequence Window & Automaton AlignmentShow value and operator stacks evaluating a parenthesized expression.
Input:ABABABCABAB
Window:ABAB
Step 1 of 6: For each token
two-expression-stacksNotes
The two-stack method is intentionally simple because full parentheses encode the evaluation order.
Sources (1)
What each reference supports for this entry.
Algorithms, 4th Edition
BookAlgorithms textbook support for Dijkstra's Two-Stack Algorithm's data-structure operations and practical implementation model.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageConceptual neighborShunting Yard Algorithm
Both use stacks to process expression operators and operands.
Alternative toPratt Parsing
Pratt parsing handles precedence directly, while the two-stack form assumes full parenthesization.
Related Algorithms
Tags
ParsingExpression ParsingStack