An infix expression is a syntactic form where operators appear between their operands (for example, a + b, a * b + c), which aligns with how humans naturally write arithmetic, but not with how machines naturally and safely evaluate precedence and associativity without ambiguity. The technically sound way to compute the numeric value of a general infix expression is to impose a formal evaluation strategy that respects operator precedence (relative priority of operators like ^, *, /, +, -), associativity (left-to-right for most operators, right-to-left for exponentiation), and parentheses as explicit grouping constructs. The canonical approach is a linear-time O(n) two‑stack algorithm that scans the input left-to-right while maintaining a stack of operands (numbers) and a stack of operators, applying operators only when doing so cannot violate the precedence and associativity rules. This technique is equivalent in spirit to Dijkstra’s shunting-yard conversion followed by postfix evaluation, but performs evaluation on the fly, thereby avoiding the intermediate postfix form. In practice, a robust evaluator must also account for multi-digit literals, whitespace, unary signs, and error conditions such as mismatched parentheses and division by zero. The result is a deterministic and memory-efficient procedure that generalizes across most arithmetic grammars and is easy to reason about, test, and extend. In what follows, you will find a compact “whole crust” section, a rigorous definition, the algorithm in numbered steps, a production-grade Java implementation, detailed walk-throughs of the code and examples, edge cases, complexity, and practical pros, cons, and applications.
Write down an algorithm to evaluate the infix expression
Before diving into details, it helps to frame infix evaluation as a constrained single-pass parsing-and-execution problem that must preserve mathematical correctness for any well-formed input. The core difficulty is that human-friendly notation embeds implicit rules: multiplication and division outrank addition and subtraction; exponentiation often binds tighter and associates to the right; and parentheses override defaults. If we naïvely read left-to-right and apply operators immediately, we risk computing incorrect results because future tokens may have higher precedence. The elegant resolution is to temporarily defer execution by using two stacks: one to hold numeric operands and one for operators. Each new token is either pushed to the appropriate stack or triggers a series of “reductions” where we pop an operator and the top two operands, compute, and push the result back. These reductions occur exactly when the operator at the top of the operator stack has higher precedence than, or equal precedence with and left-associative relative to, the incoming operator; parentheses delimit subproblems that must be fully reduced before the outer expression continues. Implemented correctly, this strategy guarantees that every operator is pushed and popped at most once, yielding linear time and space behavior in the number of tokens. The rest of this article packages the method in a clear specification and demonstrates a robust Java evaluator you can drop into coursework, interviews, or production tooling.
This section provides a concise, high-signal summary for readers who want the practical essence without wading through the full exposition. Evaluating an infix expression reliably hinges on respecting precedence, associativity, and parentheses while scanning left-to-right only once. Maintain two stacks: values (numbers) and ops (operators). For each token, if you see a number, push it to values; if you see an opening parenthesis, push it to ops; if you see a closing parenthesis, repeatedly pop-and-apply ops until the matching ‘(‘ appears; if you see an operator, repeatedly apply the top operator from ops to the top two values while the top operator has higher precedence, or the same precedence and is left-associative (do not pop on equal precedence when the incoming operator is right-associative like ‘^’). Then push the new operator. At the end, pop and apply any remaining operators. Handle unary signs by parsing signed numbers when a ‘+’ or ‘-‘ appears at the start or after ‘(‘ or another operator, and treat unary before ‘(‘ as 0 op (subexpression). This algorithm runs in O(n) time and O(n) space, is easy to unit-test with token-level invariants, and generalizes to richer grammars (functions, variables) with modest extensions. If you only keep one mental model, think “two conveyor belts”: numbers on one, operators on the other, and a rule-driven gate that fires operations exactly when it is safe to do so.
Whole Crust (TL;DR)
- Use two stacks: one for operands, one for operators.
- Scan left-to-right and push numbers; push ‘(‘; on ‘)’, reduce until ‘(‘.
- On an operator, reduce while stack-top operator outranks it (or ties and is left-associative).
- Treat ‘^’ as right-associative; do not reduce on equal precedence when incoming is ‘^’.
- Support unary +/− by parsing signed numbers or by transforming “−( … )” into “0 − ( … )”.
- End of input: reduce remaining operators; the single remaining value is the result.
- Time/space: O(n) where n = number of tokens; each operator is pushed and popped at most once.
An infix expression is a formal sequence defined over an operator alphabet and an operand alphabet in which each binary operator symbol appears syntactically between its two operand terms, optionally nested within a hierarchy of parentheses that determines grouping. More precisely, given a set of operands V (e.g., integers) and an ordered set of binary operators Σ with a precedence partial order and associativity assignment, a well-formed infix expression E over V ∪ Σ is either a single operand, a parenthesized form (E), or the concatenation E1 o E2 where o ∈ Σ and the interpretation of E is governed by precedence and associativity rules that disambiguate parse trees without explicit parentheses. In everyday arithmetic, the canonical precedence is ^ highest and right-associative, then * and / (left-associative), and finally + and – (left-associative). Parentheses produce subexpressions that must be fully evaluated before rejoining the outer computation, which may alter the default order. In the evaluation problem, our goal is to compute the denotation of E as a numeric value respecting these constraints using only a single pass and bounded auxiliary memory. The two-stack algorithm is a deterministic operational semantics that simulates a reduction system over E by staging operators until it is safe to apply them to the topmost available operands, thereby constructing the same result that would arise from evaluating the parse tree built under the grammar’s precedence and associativity rules.
Technical definition: What is an infix expression?
- Operand examples: 42, 3, 100
- Operators: ^, *, /, +, –
- Parentheses: (, )
- Associativity: ^ (right), *, /, +, – (left)
- Goal: compute a single numeric value
Operator precedence and associativity are the formal policy by which an unparenthesized infix sequence admits a unique parse. Precedence is a strict ranking: an operator with higher precedence binds more tightly to its adjacent operands than one with lower precedence, so it should be applied earlier in evaluation; for standard arithmetic, exponentiation ^ outranks multiplication and division, which in turn outrank addition and subtraction. Associativity resolves ties among operators with the same precedence: +, -, *, and / are left-associative (a − b − c is parsed as (a − b) − c), whereas ^ is typically right-associative (a ^ b ^ c is parsed as a ^ (b ^ c)). Parentheses override both rules by introducing an explicit subexpression boundary that must be fully reduced before rejoining the outer context. Any reliable algorithm must honor this triad, which is why a two-stack evaluator delays application of an incoming operator until the top-of-stack operator is not of higher precedence, or of equal precedence in the case when associativity dictates deferral (e.g., right-associative exponentiation). By codifying these rules as a short precedence function and a left/right associativity check, we gain a simple, universal mechanism to determine whether to reduce now or defer. In practice, this greatly simplifies the design of a correct evaluator and avoids ad hoc branching that is hard to test and easy to get wrong under nested and mixed-operator expressions.
Operator precedence and associativity rules (the bedrock)
- Define precedence: ^ > * = / > + = -.
- Define associativity: ^ is right-associative; others are left-associative.
- Parentheses force immediate evaluation of enclosed subexpressions before proceeding.
- During scanning, compare the incoming operator to the stack-top operator to decide whether to reduce.
The two-stack algorithm provides a deterministic, linear-time method for evaluating infix expressions by orchestrating when operators are applied to operands. Conceptually, maintain an operand stack (values) and an operator stack (ops). Traverse the expression left-to-right, token by token. When you encounter a number (including possibly signed numbers), push it onto the values stack. When you see an opening parenthesis ‘(‘, push it onto the ops stack to mark a subproblem boundary. When you encounter a closing parenthesis ‘)’, repeatedly pop an operator from ops, pop two operands from values, apply the operator, and push the result until you reach the matching ‘(‘ on ops; then discard the ‘(‘ and continue. When you encounter an operator o, you must decide whether to apply existing operators before pushing o; while the stack-top operator t has higher precedence than o, or has equal precedence and o is left-associative, pop t and apply it to the top two values; when this condition fails (or t is ‘(‘), push o. At end of input, repeatedly apply any remaining operators. Unary +/− can be handled by parsing signed numbers when a sign appears at the start or after ‘(‘ or another operator; in the special case of a unary sign directly before ‘(‘, push 0 and treat it as a binary operation with the subexpression. This disciplined sequencing ensures each operator is pushed and popped at most once, yielding O(n) time and O(n) space with clear correctness guarantees.
Algorithm to evaluate an infix expression (two-stack method)
- Initialize two empty stacks: values and ops.
- Scan tokens left-to-right:
- If token is a number, push to values.
- If token is ‘(‘, push to ops.
- If token is ‘)’, reduce until ‘(‘ appears on ops; pop ‘(‘.
- If token is an operator o:
- While ops top t is not ‘(‘ and [prec(t) > prec(o) or (prec(t) = prec(o) and o is left-associative)], pop t, pop two values, apply, push result.
- Push o.
- After scanning, reduce remaining operators.
- The single value on values is the answer.
To make this method actionable, we will implement a production-grade evaluator in Java that supports whitespace, multi-digit integers, unary signs, parentheses, standard operators (+, −, *, /, ^), and safe error handling. The implementation uses ArrayDeque for both stacks, explicit precedence and associativity functions, and a guarded reduction routine that validates operand availability and prevents illegal operations such as division by zero or mismatched parentheses. Unlike naïve left-to-right calculators, this version faithfully defers applying operators when doing so would violate precedence or associativity, which prevents common mistakes like evaluating exponent chains left-to-right or letting addition sneak in before multiplication. For integer division, we adopt Math.floorDiv to achieve mathematical floor semantics on negatives, which is often preferable in algorithmic contexts and is consistent with many DSA problem statements. Exponentiation is implemented via fast power by squaring for integer exponents. Unary plus and minus are handled via two complementary tactics: (a) parsing signed numbers when a sign appears at the start or after ‘(‘ or another operator, and (b) rewriting a unary sign before a parenthesis into an equivalent binary operation by injecting 0 to the values stack. This careful tokenization and operator discipline yields a compact, testable, and extendable solution ready for coursework, interviews, and real systems.
Java implementation (robust, production-ready)
import java.util.ArrayDeque;
import java.util.Deque;
public class InfixEvaluator {
public static long evaluate(String expr) {
if (expr == null) {
throw new IllegalArgumentException("Expression is null");
}
Deque<Long> values = new ArrayDeque<>();
Deque<Character> ops = new ArrayDeque<>();
int n = expr.length();
int i = 0;
// Tracks the kind of previous token for unary sign decisions:
// 'n' = number/operand, 'o' = operator, '(' or ')', null = start
Character prevToken = null;
while (i < n) {
char ch = expr.charAt(i);
// Skip whitespace
if (Character.isWhitespace(ch)) {
i++;
continue;
}
// Opening parenthesis
if (ch == '(') {
ops.push(ch);
prevToken = '(';
i++;
continue;
}
// Number (with optional leading sign in specific contexts)
if (Character.isDigit(ch) ||
((ch == '+' || ch == '-') && isUnarySignContext(prevToken) && hasNextDigit(expr, i + 1))) {
int sign = 1;
if (ch == '+' || ch == '-') {
sign = (ch == '-') ? -1 : 1;
i++;
// Allow spaces between sign and digits
while (i < n && Character.isWhitespace(expr.charAt(i))) i++;
if (i >= n || !Character.isDigit(expr.charAt(i))) {
throw new IllegalArgumentException("Invalid signed number near index " + (i - 1));
}
}
long num = 0;
boolean hasDigits = false;
while (i < n && Character.isDigit(expr.charAt(i))) {
hasDigits = true;
num = num * 10 + (expr.charAt(i) - '0');
i++;
}
if (!hasDigits) {
throw new IllegalArgumentException("Expected digits for number near index " + i);
}
values.push(sign * num);
prevToken = 'n';
continue;
}
// Closing parenthesis: reduce until matching '('
if (ch == ')') {
while (!ops.isEmpty() && ops.peek() != '(') {
applyTop(values, ops);
}
if (ops.isEmpty() || ops.peek() != '(') {
throw new IllegalArgumentException("Mismatched parentheses near index " + i);
}
ops.pop(); // discard '('
prevToken = ')';
i++;
continue;
}
// Operator
if (isOperator(ch)) {
// Handle unary sign before '(' by transforming: -( ... ) -> 0 - ( ... )
if ((ch == '+' || ch == '-') && isUnarySignContext(prevToken) && nextNonSpaceIsParen(expr, i + 1)) {
values.push(0L);
}
// Reduce while it is safe and necessary to do so
while (!ops.isEmpty() && ops.peek() != '(' &&
(hasHigherPrecedence(ops.peek(), ch) ||
(hasEqualPrecedence(ops.peek(), ch) && isLeftAssociative(ch)))) {
applyTop(values, ops);
}
ops.push(ch);
prevToken = 'o';
i++;
continue;
}
throw new IllegalArgumentException("Unexpected character '" + ch + "' at index " + i);
}
// Final reductions
while (!ops.isEmpty()) {
if (ops.peek() == '(') {
throw new IllegalArgumentException("Mismatched '(' remaining on operator stack");
}
applyTop(values, ops);
}
if (values.size() != 1) {
throw new IllegalArgumentException("Invalid expression: leftover operands");
}
return values.pop();
}
private static boolean isUnarySignContext(Character prev) {
return prev == null || prev == '(' || prev == 'o';
}
private static boolean hasNextDigit(String s, int idx) {
while (idx < s.length() && Character.isWhitespace(s.charAt(idx))) idx++;
return idx < s.length() && Character.isDigit(s.charAt(idx));
}
private static boolean nextNonSpaceIsParen(String s, int idx) {
while (idx < s.length() && Character.isWhitespace(s.charAt(idx))) idx++;
return idx < s.length() && s.charAt(idx) == '(';
}
private static boolean isOperator(char c) {
return c == '+' || c == '-' || c == '*' || c == '/' || c == '^';
}
private static int precedence(char op) {
switch (op) {
case '^': return 3;
case '*':
case '/': return 2;
case '+':
case '-': return 1;
default: return 0;
}
}
private static boolean isLeftAssociative(char op) {
// Only '^' is right-associative in our grammar
return op != '^';
}
private static boolean hasHigherPrecedence(char a, char b) {
return precedence(a) > precedence(b);
}
private static boolean hasEqualPrecedence(char a, char b) {
return precedence(a) == precedence(b);
}
private static void applyTop(Deque<Long> values, Deque<Character> ops) {
if (values.size() < 2) {
throw new IllegalArgumentException("Insufficient operands for operation");
}
long b = values.pop();
long a = values.pop();
char op = ops.pop();
long r;
switch (op) {
case '+': r = a + b; break;
case '-': r = a - b; break;
case '*': r = a * b; break;
case '/':
if (b == 0) throw new ArithmeticException("Division by zero");
r = Math.floorDiv(a, b);
break;
case '^':
if (b < 0) {
throw new IllegalArgumentException("Negative exponent not supported for integer power");
}
r = pow(a, b);
break;
default:
throw new IllegalArgumentException("Unknown operator: " + op);
}
values.push(r);
}
private static long pow(long base, long exp) {
long res = 1;
long b = base;
long e = exp;
while (e > 0) {
if ((e & 1L) == 1L) res *= b;
b *= b;
e >>= 1;
}
return res;
}
// Simple demo
public static void main(String[] args) {
String[] tests = {
"100 + 200 / 2 * 5 + 7",
"2 ^ 3 ^ 2",
"-(3 + 4) * 5",
"3 + -4 * (2 + 1)",
"((2 + 3) * 4) ^ (1 + 1)"
};
for (String t : tests) {
System.out.println(t + " = " + evaluate(t));
}
}
}Understanding a program like this is easiest if we decompose its behavior into small, verifiable responsibilities and then track how those responsibilities compose in a single pass. The entry point evaluate prepares two ArrayDeque stacks: one storing Long values, the other storing operator chars. As we iterate across the input string, we normalize whitespace and classify each next token. A number may include a unary sign if it appears at the start of the expression, after an opening parenthesis, or after another operator; such contexts are flagged by prevToken and validated using lookahead routines that confirm digits follow or a parenthesis follows in the case of unary before ‘(‘. Parentheses are treated as segmentation markers: ‘(‘ is pushed to the operator stack, while ‘)’ drains operators until the matching ‘(‘ surfaces. The crux is the operator ingestion rule: we repeatedly reduce the stack while the top operator would bind more tightly than the incoming operator (or equally tightly and the incoming operator is left-associative), because delaying such a top operator would violate the grammar. Each reduction pops two operands and a single operator, applies the operation (with explicit checks for division by zero and unsupported negative exponents), and pushes the result back. The pass concludes by draining any remaining operators; the operand stack must then contain exactly one value, which is the final result. Auxiliary helpers keep the code readable and testable: precedence, associativity, unary context detection, safe lookahead, fast exponentiation, and a guarded applyTop that fails fast on malformed inputs.
Step-by-step explanation of the Java program
- Initialization
- Create values (operands) and ops (operators) stacks; set prevToken to null to indicate “start-of-expression” context.
- Token scanning
- Skip spaces eagerly to keep logic simple and robust.
- On ‘(‘ push to ops; on ‘)’ pop-and-apply until ‘(‘ is found, then discard it.
- Numbers and unary signs
- If the current char is a digit, parse a full multi-digit integer.
- If it is a sign in a unary context (start, after ‘(‘, or after an operator) and followed by digits, parse a signed integer.
- If it is a sign in a unary context followed by ‘(‘, push 0 to values and treat the sign as a binary operator applied to the upcoming parenthesized subexpression.
- Operators and reductions
- Before pushing an incoming operator o, while top operator t on ops has higher precedence than o, or the same precedence and o is left-associative, repeatedly reduce: pop t, pop two values a and b, compute a t b, push result.
- Push o after those safe reductions; this enforces precedence and associativity.
- End of input
- Drain remaining operators with the same reduction rule; ensure no stray ‘(‘ remains.
- Check that exactly one value remains; return it.
- Safety and correctness
- applyTop throws on insufficient operands, division by zero, unknown operators, and negative exponents.
- Mismatched parentheses and unexpected characters raise descriptive exceptions.
Examples are essential to build intuition because they exercise the evaluation policy under realistic token interleavings and confirm that precedence/associativity decisions happen at the correct moments. Think of two conveyor belts: one belt carries numbers in the order they appear; the other queues operators. A gate between them pops from the operator belt and consumes the top two numbers only when it is safe to do so—i.e., when this operator is guaranteed to execute before any incoming operator based on the grammar. Example 1 (100 + 200 / 2 * 5 + 7) shows chaining of mixed precedence: division and multiplication reduce early even though addition spans the whole sequence; the final answer must be 607. Example 2 (2 ^ 3 ^ 2) highlights right-associativity of exponentiation: the correct parse is 2 ^ (3 ^ 2) = 2 ^ 9 = 512; if you treat ^ as left-associative, you would incorrectly compute (2 ^ 3) ^ 2 = 64. Example 3 (-(3 + 4) * 5) validates unary-before-parenthesis handling by rewriting it to 0 − (3+4) first, then multiplying the result by 5; the answer is −35. Dry-running these cases reinforces when reductions happen and why deferring certain operators preserves correctness.
Worked examples and dry runs
Example 1: 100 + 200 / 2 * 5 + 7
- Read 100 → push 100.
- Read + → ops: [+].
- Read 200 → push 200.
- Read / → higher than +, push ‘/’.
- Read 2 → push 2; next operator * has same precedence as / and is left-associative → reduce: 200 / 2 = 100; push 100; push ‘*’.
- Read 5 → push 5; next + → reduce: 100 * 5 = 500; now top is + (same as incoming + and left-associative) → reduce: 100 + 500 = 600; push incoming +.
- Read 7 → push 7; end → reduce: 600 + 7 = 607 → result 607.
Example 2: 2 ^ 3 ^ 2
- Read 2 → push 2.
- Read ^ → push ‘^’.
- Read 3 → push 3.
- Read ^ → since incoming ‘^’ is right-associative, do not reduce on equal precedence → push ‘^’.
- Read 2 → push 2; end → reduce rightmost first: 3 ^ 2 = 9; then 2 ^ 9 = 512.
Example 3: -(3 + 4) * 5
- Unary ‘-‘ before ‘(‘ → push 0, push ‘-‘.
- ‘(‘ → push ‘(‘.
- 3 → push 3; + → push ‘+’; 4 → push 4; ‘)’ → reduce: 3 + 4 = 7; pop ‘(‘.
- Now stacks: values [0, 7], ops [‘-‘]; next * has higher precedence than ‘-‘ → push ‘*’.
- 5 → push 5; end → reduce: 7 * 5 = 35; then 0 – 35 = -35.
Complexity analysis for the two-stack evaluator is straightforward once you observe that each operator is pushed and popped at most once, and each operand is pushed once and participates in exactly one binary operation. Tokenization is linear in the number of characters when parsing multi-digit integers and skipping whitespace. Reductions either happen immediately upon encountering a new operator or are deferred until a closing parenthesis or end-of-input, but the total number of reductions matches the number of operators. Memory usage is bounded by the maximum depth of nested parentheses and the number of deferred operators, which in the worst case is linear in tokens. In other words, even though evaluation appears to “jump” backward when a high-precedence operator appears late, the algorithm never rescans earlier segments; it merely consumes previously staged operators in stacks, which is an amortized constant-time pop. The table below summarizes the complexities for each core phase. Note that if you extend the grammar with functions or variables requiring environment lookups or symbol resolution, the asymptotic bounds remain the same provided each token is still processed a constant number of times and function arities are bounded.
Time and space complexity
| Component | Description | Complexity |
|---|---|---|
| Tokenization | Scan characters, skip spaces, parse multi-digit integers and unary signs | O(n) |
| Operator handling | Each operator is pushed and popped at most once; precedence/associativity checks are O(1) | O(n) |
| Parentheses processing | Push on ‘(‘; pop until ‘(‘ on ‘)’ with constant-time stack operations | O(n) |
| Overall time | Single left-to-right pass with amortized constant-time operations | O(n) |
| Space | Stacks for operands and operators; worst-case proportional to tokens | O(n) |
Beyond correctness and linear performance, it is helpful to evaluate the approach pragmatically in terms of strengths, trade-offs, and where it shines in real systems. The two-stack method’s main advantage is that it directly encodes the semantics of precedence and associativity without building an explicit parse tree or emitting a postfix intermediate form, which both improves speed and reduces memory pressure. Its stepwise reductions make debugging easy—each pop/apply/push operation is a verifiable micro-step. The principal trade-offs involve unary operators, integer division semantics across languages, and exponentiation overflow behavior, which require explicit, well-documented design choices. In practice, this method generalizes naturally to calculators, interpreters, and compilers that either evaluate directly or first convert to an AST, and to data systems (like spreadsheets and rules engines) that repeatedly evaluate expressions safely and predictably. The bullet points below distill these considerations so you can decide how to adapt the method to your own constraints, grading rubrics, or production requirements, and also highlight how to extend it to richer grammars (functions, variables, constants like pi) without losing its linear-time edge.
Advantages, disadvantages, and applications
Advantages
- Correctness by construction: strictly enforces precedence, associativity, and parentheses.
- Performance: single-pass O(n) time and O(n) space; each operator is processed twice (push, pop) at most.
- Simplicity: minimal data structures (two stacks), straightforward invariants, and easy unit testing at token and reduction boundaries.
- Extensibility: can incorporate functions (e.g., sin, max), constants, and variables with a small token layer and arity-aware reductions.
- Determinism: predictable behavior that matches textbook semantics; easy to reason about and debug with dry runs.
Disadvantages
- Unary complexity: needs careful handling for unary operators, particularly signs placed before parentheses or variables.
- Division semantics: languages differ (truncation vs floor); explicit choice (e.g., floorDiv) is required to avoid surprises.
- Exponentiation overflow: integer power can overflow quickly; large exponents or bases may require BigInteger or floating types.
- Error messaging: stack-based failures can be cryptic without deliberate, user-friendly diagnostics for mismatches and arity errors.
Applications
- Calculator engines and REPLs needing safe, predictable arithmetic semantics.
- Compilers/interpreters: direct evaluators, shunting-yard conversion to postfix, or as a stepping stone to AST construction.
- Spreadsheet formula evaluators and rules engines where precedence must be exact and evaluation must be efficient.
- Query languages and configuration DSLs embedding arithmetic expressions.
Many bugs in expression evaluators arise from subtle token-context mistakes rather than the core reduce/push logic. For example, misclassifying a unary minus as a binary minus leads to “insufficient operands” errors during reductions, which can be avoided by tracking the previous token class and looking ahead for digits or parentheses. Another common pitfall is mishandling exponentiation associativity; treating ‘^’ as left-associative yields wrong results for chains like 2 ^ 3 ^ 2. Parentheses mismatches are also frequent—robust validators should fail-fast both at encountering a stray ‘)’ and at the end when ‘(‘ remains. Integer division semantics must be explicit: mathematical floor division differs from truncation toward zero on negatives; choose and document one behavior. Overflow is a practical concern for *, ^, and even +; consider BigInteger for unbounded arithmetic or detect overflow to raise informative errors. Finally, remember to forbid applying an operator when fewer than two operands are available; this guard both signals malformed expressions and prevents undefined behavior. The enumerated checklist below summarizes these issues so you can proactively test them.
Common pitfalls and edge cases
- Unary sign handling: treat signs at start/after ‘(‘ or operator as unary; rewrite “−( … )” as “0 − ( … )” or parse signed numbers.
- Right-associative ‘^’: do not reduce on equal precedence when the incoming operator is ‘^’.
- Mismatched parentheses: detect both stray ‘)’ and leftover ‘(‘ at end; report positions clearly.
- Division by zero: raise a specific error; do not silently return 0 or infinity in integer mode.
- Integer division semantics: decide truncation vs floor; this implementation uses Math.floorDiv.
- Overflow: consider BigInteger or checks when handling large products and powers.
- Invalid tokens or insufficient operands: validate and surface meaningful diagnostics early.
To conclude, evaluating infix expressions correctly and efficiently is best treated as a disciplined streaming reduction problem governed by precedence, associativity, and parentheses. The two-stack algorithm provides a compact, linear-time solution that precisely encodes these rules using constant-time decisions at each token, without constructing an explicit parse tree or emitting postfix as an intermediate form. The Java implementation here balances rigor and practicality: it supports whitespace, multi-digit integers, unary signs, parentheses, the standard operator set including right-associative exponentiation, and guarded error paths such as division by zero and mismatched parentheses. If you need floating-point arithmetic, identifiers, or function calls, extend the tokenizer to emit appropriate tokens and add arity-aware reductions for function nodes while keeping the same evaluation skeleton and complexity guarantees. For pedagogy and interviews, emphasize why reductions occur (or are deferred) at each step, and dry-run classic corner cases like 2 ^ 3 ^ 2 and −(a + b) to demonstrate associativity and unary correctness. With these tools and habits, you can build evaluators that are both theoretically sound and robust in practice.
Conclusion and further extensions
- Support variables by mapping identifiers to values before or during evaluation.
- Add functions with a function stack or by encoding them as high-precedence operators with known arity.
- Switch to BigInteger for arbitrary-precision integer arithmetic if overflow is a concern.
- Instrument with logs or counters to visualize reductions during teaching and debugging.