Calculator with two stacks

Why this matters

A calculator app, a spreadsheet cell with a formula, and a search filter like price > 10 and stock > 0 all need to turn text into a value. The first step is to read the symbols in the right order. The previous lesson in this module showed how to rewrite an infix expression into postfix. This lesson skips that rewrite and computes the value directly, in one pass over the text, using two stacks.

The method is Dijkstra's two-stack algorithm, the same person who gave the shunting-yard method. It is short, and it shows how two simple piles can handle brackets and precedence together.

You will build a small calculator in C++. It handles whole numbers, the four operators +, -, * and /, and round brackets. Each program was compiled with g++ -std=c++20 -Wall -Wextra and run, and the output below is copied from those runs.

Words used in this lesson

A value is a number the calculator holds while it works, such as 3 or 14.

An operand stack is a stack that holds values. An operator stack is a stack that holds operator symbols and opening brackets. A stack is a pile where you add and remove items only at the top. The last item pushed is the first item popped. In C++ the type is std::stack, from the <stack> header.

Precedence is the rule that decides which operator goes first. * and / bind tighter than + and -.

Associativity decides the order when two operators have equal precedence. Subtraction runs left to right. 8 - 3 - 2 means (8 - 3) - 2.

Integer division keeps only the whole part of a quotient. 100 / 7 is 14, not 14.28..., because the calculator only works with whole numbers here.

To apply an operator means to take the values it needs off the operand stack, compute the result, and push the result back.

The two rules that drive everything

The method uses two piles and two rules.

The operand stack holds numbers that are waiting to be used. The operator stack holds operators that are waiting for their right-hand value, plus any opening brackets.

Read the text from left to right, one token at a time. The rules are:

1. A number. Push it onto the operand stack.
2. An opening bracket. Push it onto the operator stack.
3. A closing bracket. Apply operators from the operator stack until you reach the matching opening bracket. Then remove that bracket. The brackets are done, so the value inside them now sits on the operand stack as a single value.
4. An operator. Before you push it, look at the top of the operator stack. While that top is an operator that binds at least as tightly as the new one, apply it. Then push the new operator.
5. End of text. Apply every operator left on the operator stack, one at a time.

Rule 4 is the heart of the method. Think about why it is safe. An operator on the stack has already read its left-hand value. If the new operator binds tighter, the operator on the stack must wait, because its right-hand value is not finished yet. If the new operator binds less tightly or equally, the operator on the stack can be done now.

Rule 3 handles brackets the same way. Everything inside brackets must be finished before the brackets close, so the calculator applies operators until it reaches the (.

Why two stacks

A value waits until an operator needs it. An operator waits until its right-hand value has been read. A single pile cannot keep both kinds of waiting item in order, because values and operators can be mixed in any order. With two piles, each kind has its own place, and the top of each pile is always the next item that matters.

Think of a kitchen with two counters. One counter holds finished plates of food, which are the values. The other holds written instructions that still need a plate, which are the operators. When a new instruction comes in, the cook first finishes any older instruction that must go first, using the top plates. Then the new instruction goes on the second counter. The plates and the instructions never mix.

Worked example 1: 3 + 4 * 2

The table below uses two columns of stacks. Each list is written from bottom to top, so the last item in a list is the top. The last column names the rule used on that row.

The * stayed on the operator stack when it arrived, because the + below it binds less tightly. The * was applied first at the end, because it was on top. The + was applied last. The result is 11, which is what the expression means in ordinary maths.

Now try the same rules on 3 * 4 + 2. When the + arrives, the * is on top and binds at least as tightly, so * is applied first: 3 * 4 gives 12. Then the + is pushed. At the end, 12 + 2 gives 14. The rules handle both orders without any special case.

Worked example 2: brackets

Take (1 + 2) * (3 + 4). The value should be 3 * 7 = 21.

1. ( is pushed. Operators: (.
2. 1 is pushed. Values: 1.
3. + is pushed. The top is (, which is not an operator, so nothing is applied. Operators: (, +.
4. 2 is pushed. Values: 1, 2.
5. ) applies +, giving 3. The ( is removed. Values: 3. Operators: empty.
6. * is pushed onto the empty operator stack. Operators: *.
7. ( is pushed. Operators: *, (.
8. 3 is pushed. Values: 3, 3.
9. + is pushed. Operators: *, (, +.
10. 4 is pushed. Values: 3, 3, 4.
11. ) applies +, giving 7. The ( is removed. Values: 3, 7. Operators: *.
12. End of text applies *, giving 21.

The bottom 3 in step 8 is the result of the first bracket group, and the 3 pushed on top of it is the literal number from the second group. The stack keeps them apart without any extra work.

Worked example 3: division and associativity

Take 100 / 7 - 3 * (2 + 1). This expression mixes all four operators and brackets, and it shows integer division.

1. 100 is pushed. Values: 100.
2. / is pushed onto the empty operator stack. Operators: /.
3. 7 is pushed. Values: 100, 7.
4. - arrives. The top / binds at least as tightly as -, so it is applied: 100 / 7 gives 14, because the calculator keeps only the whole part. Values: 14. Then - is pushed. Operators: -.
5. 3 is pushed. Values: 14, 3.
6. * arrives. The top is -, which binds less tightly, so * is pushed. Operators: -, *.
7. ( is pushed. Operators: -, *, (.
8. 2 and + and 1 are read, as in example 2. Inside the brackets the + is applied at ), giving 3. Values: 14, 3, 3. Operators: -, *.
9. End of text applies *: 3 * 3 gives 9. Values: 14, 9. Operators: -.
10. End of text applies -: 14 - 9 gives 5.

The result is 5. The Common mistakes section shows what a strict comparison in rule 4 does, with real output. It matters only for operators of equal precedence.

The program

The program below does all of the above. It reads the text one character at a time. The expect_value flag is true when the next token must be a number or an opening bracket, and false when it must be an operator or a closing bracket. The flag is how the program catches input like -3 + 4, where an operator appears before any value.

#include <cctype>
#include <iostream>
#include <stack>
#include <stdexcept>
#include <string>
 
int precedence(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;
}
 
// Pop two values, apply one operator, and push the result back.
void apply_top(std::stack<long long>& values, char op) {
    if (values.size() < 2) {
        throw std::invalid_argument("operator needs two values");
    }
    const long long right = values.top();
    values.pop();
    const long long left = values.top();
    values.pop();
 
    switch (op) {
        case '+': values.push(left + right); break;
        case '-': values.push(left - right); break;
        case '*': values.push(left * right); break;
        case '/':
            if (right == 0) {
                throw std::domain_error("division by zero");
            }
            values.push(left / right);
            break;
        default:
            throw std::invalid_argument(std::string("unknown operator '") + op + "'");
    }
}
 
long long evaluate(const std::string& text) {
    std::stack<long long> values;
    std::stack<char> ops;
    bool expect_value = true;  // true when the next token must be a number or "("
    std::size_t i = 0;
 
    while (i < text.size()) {
        const char c = text[i];
 
        if (std::isspace(static_cast<unsigned char>(c))) {
            ++i;
        } else if (std::isdigit(static_cast<unsigned char>(c))) {
            if (!expect_value) {
                throw std::invalid_argument("missing operator before a number");
            }
            long long number = 0;
            while (i < text.size() && std::isdigit(static_cast<unsigned char>(text[i]))) {
                number = number * 10 + (text[i] - '0');
                ++i;
            }
            values.push(number);
            expect_value = false;
        } else if (c == '(') {
            if (!expect_value) {
                throw std::invalid_argument("missing operator before '('");
            }
            ops.push(c);
            ++i;
        } else if (c == ')') {
            if (expect_value) {
                throw std::invalid_argument("missing value before ')'");
            }
            while (!ops.empty() && ops.top() != '(') {
                apply_top(values, ops.top());
                ops.pop();
            }
            if (ops.empty()) {
                throw std::invalid_argument("unmatched ')'");
            }
            ops.pop();  // throw away the "("
            expect_value = false;
            ++i;
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            if (expect_value) {
                throw std::invalid_argument(std::string("expected a value before '") + c + "'");
            }
            while (!ops.empty() && ops.top() != '(' &&
                   precedence(ops.top()) >= precedence(c)) {
                apply_top(values, ops.top());
                ops.pop();
            }
            ops.push(c);
            expect_value = true;
            ++i;
        } else {
            throw std::invalid_argument(std::string("unknown character '") + c + "'");
        }
    }
 
    if (expect_value) {
        throw std::invalid_argument("expression ends too early");
    }
    while (!ops.empty()) {
        if (ops.top() == '(') {
            throw std::invalid_argument("unmatched '('");
        }
        apply_top(values, ops.top());
        ops.pop();
    }
    if (values.size() != 1) {
        throw std::invalid_argument("expression is incomplete");
    }
    return values.top();
}
 
int main() {
    const std::string examples[] = {
        "3 + 4 * 2",
        "(1 + 2) * (3 + 4)",
        "100 / 7 - 3 * (2 + 1)",
        "8 - 3 - 2",
        "20 / 4 / 5",
        "7 / 0",
        "-3 + 4",
        "(2 + 3",
        "2 + 3)",
        "2 + * 3",
    };
 
    for (const std::string& text : examples) {
        std::cout << text << " = ";
        try {
            std::cout << evaluate(text) << "\n";
        } catch (const std::exception& e) {
            std::cout << "error: " << e.what() << "\n";
        }
    }
    return 0;
}

Compile and run it:

g++ -std=c++20 -Wall -Wextra -o calc calc.cpp && ./calc

The output is:

3 + 4 * 2 = 11
(1 + 2) * (3 + 4) = 21
100 / 7 - 3 * (2 + 1) = 5
8 - 3 - 2 = 3
20 / 4 / 5 = 1
7 / 0 = error: division by zero
-3 + 4 = error: expected a value before '-'
(2 + 3 = error: unmatched '('
2 + 3) = error: unmatched ')'
2 + * 3 = error: expected a value before '*'

Every value matches the hand traces above. 20 / 4 / 5 gives 1 because 20 / 4 is 5 and 5 / 5 is 1. Reading it the other way would give 20 / 0, which is an error, so the left-to-right rule is what makes the program work.

Here is how the pieces fit together. apply_top does the actual arithmetic, one operator at a time. It pops the right-hand value first and the left-hand value second. This order matters for subtraction and division. If the code popped the left value first, 10 - 4 would become 4 - 10. The evaluate function does the scanning and calls apply_top at the points that rules 3, 4 and 5 describe.

The isspace, isdigit and similar functions come from <cctype>. They expect a value that fits in an unsigned char, which is why the code casts each character before the call.

Test inputs and what they return

The main function runs a fixed list. To try other inputs, call evaluate with any text. The table below comes from a copy of the program whose main runs these inputs through the same evaluate function:

The line 10 / 3 * 3 shows integer division. 10 / 3 is 3, and 3 * 3 is 9. The lost part of the division never comes back, so the answer is not 10. A calculator that must keep fractions needs a different number type, such as double, and a different way to print the result.

Common mistakes

Using > where >= is needed. Rule 4 applies operators that bind at least as tightly. If the comparison is strict, two operators with equal precedence stay on the stack, and the right-hand one is applied last. Here is the line for 8 - 3 - 2 from the same program with > in the comparison:

8 - 3 - 2 = 7

The program computed 8 - (3 - 2), which is 7, instead of (8 - 3) - 2, which is 3. Test left-to-right behaviour with a case like 8 - 3 - 2 or 20 / 4 / 5. A single operator, such as 3 + 4, will never show the mistake.

Popping in the wrong order. Both apply_top and the users of it must take the right-hand value first. Popping the left value first reverses subtraction and division. Check any new operator with an input where the order matters, such as 10 - 4 and 20 / 5.

Forgetting the check for a missing value. The expect_value flag catches input like -3 + 4. The program reports:

-3 + 4 = error: expected a value before '-'

A calculator that accepts a leading minus must handle it on purpose, for example by treating it as a negative number. This program does not, so the flag turns the input into a clear error instead of a wrong answer.

Applying from an empty stack. std::stack::top() and pop() on an empty stack are undefined behaviour in C++. The program may print junk, crash, or appear to work. The values.size() < 2 check in apply_top stops this for the calculator. If you remove it, or use a stack that has been emptied by an earlier bug, the standard library can detect the problem when you compile with -D_GLIBCXX_ASSERTIONS. Here is the message from a small program that calls top() after pop() on a one-item stack, compiled with that flag:

/usr/include/c++/15/bits/stl_stack.h:260: std::stack<_Tp, _Sequence>::reference std::stack<_Tp, _Sequence>::top() [with _Tp = int; _Sequence = std::deque<int, std::allocator<int> >; reference = int&]: Assertion '!this->empty()' failed.

The program then stops with exit code 134, which means it was aborted. The file path and line number depend on the compiler version. The line in the message points at the standard library header, not at your code, so look at your own call that caused it.

Division by zero. 7 / 0 reports error: division by zero. The program checks the divisor before dividing, because dividing by zero in C++ for integers is undefined behaviour and may crash the program.

Overflow. The values use long long, a whole-number type with at least 64 bits. A result larger than about 9 * 10^18 is outside its range. Signed overflow is undefined behaviour in C++, so the result cannot be trusted. This lesson does not check for it. A calculator that must handle very large numbers needs its own check before each operation.

Practice

Exercise 1. Evaluate 2 + 3 * 4 by hand with two stacks. Write the value stack and the operator stack after each token.

Show the answer

After 2, the values are 2. After +, the operators are +. After 3, the values are 2, 3. The * is pushed on top of +, because * binds tighter, so the operators are +, *. After 4, the values are 2, 3, 4. At the end, * gives 12, and then + gives 14.

Exercise 2. Evaluate (2 + 3) * 4 by hand.

Show the answer

The ( is pushed and the + sits above it. At ), the + is applied to get 5, and the ( is removed. The * is then pushed onto the empty operator stack. The value stack is 5, 4. At the end, * gives 20.

Exercise 3. Work out the value of 15 / 4 * 2 by hand. Remember that division keeps only the whole part.

Show the answer

The answer is 6. The / is pushed, and then the * arrives. The two operators have equal precedence, so the / is applied first. 15 / 4 is 3, because the whole part of 3.75 is kept. Then 3 * 2 gives 6. Doing 4 * 2 first would give 15 / 8, which is 1, so the left-to-right rule matters here.

Exercise 4. Explain why 1 - 2 - 3 gives -4, not 2.

Show the answer

Subtraction is left-associative, so 1 - 2 - 3 means (1 - 2) - 3. The first - is applied when the second - arrives, giving -1. Then -1 - 3 gives -4. If subtraction were right-associative, the expression would mean 1 - (2 - 3), which is 2.

Exercise 5. Add the % operator, which gives the remainder after division, with the same precedence as * and /. Name every place in calc.cpp that must change.

Show the answer

There are three places. In precedence, add % to the line that returns 2. In evaluate, add c == '%' to the test that detects operators. In apply_top, add a case '%': that pushes left % right, and check for a zero divisor the same way the / case does. The rest of the program stays the same, because the two-stack rules do not depend on which operator is used.

Summary

• A calculator with two stacks keeps values on one stack and operators on another.
• Each new operator first applies every operator on the stack that binds at least as tightly.
• A closing bracket applies operators until the matching opening bracket, then removes it.
• At the end of the text, every operator left on the stack is applied.
• Test left-to-right behaviour with equal operators, such as 8 - 3 - 2, because a strict comparison gives a wrong answer that looks plausible.