Evaluating Expressions: Dijkstra's 2 Stack Algorithm

mgcadmin 19-09-2023

A couple of years back I interviewed for an SDE role at Amazon. For those not familiar with the Amazon hiring process, after you pass there screening technical test, and a personality evaluation, the final part before being given an offer involves a multi-part day long technical interview where you do coding exercises on a white board with each of the different interviewers, usually around 5 lasting 45 minutes to an hour each.

My first exercise was to implement a spreadsheet like program, not bad, wasn't expecting something so involved as the opener, but I managed fine. I worked through the problem and then began my second round with the next interviewer: Implement the game 'Snake'. This was right up my alley and I breezed through it. Feeling confident after swiftly handling my first two challenges, I was feeling relaxed going in to the third round.

As part of their interview process, Amazon makes use of what they call a "Bar raiser" - an interviewer whos job it is to specifically up the ante, providing a more difficult challenge. After exchanging pleasantries the interviewer wrote out two longish math equations, and asked me to write a program to evaluate them, respecting the order of operations.

My mind went completely blank. It was as if he just asked me to do a backflip: I couldn't for the life of me even figure out where to begin. I fleetingly remembered something about a type of binary tree, and maybe something to do with a stack... and Dijkstra? I spent so much time studying sorting, and graphs, I could implement red black trees from scratch! Why hadn't I studied this? In truth, I had studied evaluating expressions, but in a moment of panic, my anxiety completely took the wind out of my sails, and it was as if I hadn't prepared at all. In the end I was able to piece together a really ugly function that did all sorts of string chopping and repeated runs iterating over the string. If memory recalls the strategy I came up with was to find the inner most pair of parentheses, solve that and replace it with its value, and repeat, working my way out until there were no more parentheses. Just generally hacked together and fragile way for solving the problem, certainly not canonical, and definitely was not what the interviewer had in mind when he proposed the question.

The next two rounds after went much smoother, but the experience left a distinct impression. In the end I suppose the interview went well enough, as Amazon offered me a SDE role.(Which I ended up turning down, but that's a story for a different post.)

In this post I'm going to go over Dijkstras 2 stack algorithm, which is a very simple way of solving this problem in an interview setting - in the real world, there are much better ways to go about it.

Dijkstra's 2 Stack Algorithm

When faced with evaluating expressions, you have operators and operands. The operators operate on the operands, got it? Good. In case you don't, that means in the expressions '2 + 3', the operator is the '+' sign, and the operands are the numbers.

Operators also have precedence, which can be overridden with the use of parentheses(See P.EM.D.A.S.). Coincidentally, there exists a way to write equivalent expressions which still obey the order of evaluation without the use of parentheses. This is called Postfix Notation, and it expressions written this way posses the desirable quality that it is a simple affair to evaluate these expressions using just 1 stack.

Unfortunately for us, the expressions provided as input to our program are in infix notation. At this point I could use the shunting yard algorithm to convert the infix expression to postfix notation. But that isn't strictly necessary. Instead, we can evaluate infix expressions without converting them to postfix: we use 2 stacks and evaluate as we go.

This is personal preference, but I find the default behavior of std::stack<T>::pop() to be done poorly, so whenever I know I'm going to be using a stack the first thing I like to do is override the STL stack implementations version of pop to return the value being popped from the stack instead of being a void function:

#include <iostream>
#include <stack>
using namespace std;

template <class T>
struct Stack : public stack<T> {
    T pop() {
        T ret = stack<T>::top();
        stack<T>::pop();
        return ret;
    }
}; 

Next up, we already know we are going to be taking two numbers and doing one of four operations of to them, so a very simple DFA in the form of the following function makes sense:

int applyOper(char op, int a, int b) {
        switch (op) {
            case '+':
                cout<<a<<" + "<<b<<" = "<<(a +b )<<endl;
                return (a +b );
            case '*':
                cout<<a<<" * "<<b<<" = "<<(a * b)<<endl;
                return (a * b);
            case '/':
                cout<<a<<" / "<<b<<" = "<<(a / b)<<endl;
                return (a / b);
            case '-':
                cout<<a<<" - "<<b<<" = "<<(a - b)<<endl;
                return (a - b);
        }
    return 0;
} 

Now to evaluate our expressions, we declare a function that takes as input the expression as a string, and will return the value derived from evaluating it.

The algorithm being implemented was invented by Edsgar Dijkstra, and utilizes two stacks: one stack for holding operators, and one stack for holding operators. The expression string is iterate over, with operators being pushed on to the operator stack, with the exception of open and closing parentheses. blank spaces are ignored, and values are placed on the value stack. when a closing parentheses is encountered, the enclosing scope just iterated over is calculated by applying the stored operators to the stored operands. If at the end, there are still operators, they are also all used in the same way.

 int eval(string str) {
    int x, a, b;
    char op;
    Stack<int> vals;
    Stack<char> ops;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(' || str[i] == ' ') {
            continue;
        } else if (str[i] == '+' || str[i] == '*' ||str[i] == '-' || str[i] == '/' ) { 
            //push valid operators to stack.
            cout<<"push: "<<str[i]<<endl;
            ops.push(str[i]);
        } else if (str[i] == ')') { 
            //replace expression in paren's with its value.
            b = vals.pop();
            a = vals.pop();
            vals.push(applyOper(ops.pop(), a, b));
        } else if (isdigit(str[i])) {
            //convert string to digit and push to value stack.
            int e = i;
            while (isdigit(str[++e]));
            x = atoi(str.substr(i, e).c_str());
            vals.push(x);
            cout<<"push: "<<x<<endl;
            i = e-1;
        } 
    }
    while (!ops.empty()) {
        b = vals.pop();
        a = vals.pop();
        op = ops.pop();
        vals.push(applyOper(op, a, b));
        cout<<"push: "<<vals.top()<<endl;
    }
    cout<<"answer: "<<vals.top()<<endl;
    return vals.pop();
} 

As I said, this is the kind of solution to reach for in an interview: less than a page of code, It's easy enough to "step through" on a white board, and most importantly: it does what was asked. 

 
int main() {
    cout<<eval("10 + 2 * 6")<<endl;
    cout<<eval("(10+2)*6")<<endl;
    cout<<eval("(100 * 2) + 12")<<endl;
    cout<<eval("((100/2)-(25/3))+85")<<endl;
} 
max@MaxGorenLaptop:~/DSA$ ./eval
 push: 10
 push: +
 push: 2
 push: *
 push: 6
 2 * 6 = 12
 push: 12
 10 + 12 = 22
 push: 22
 answer: 22

 push: 10
 push: +
 push: 2
 10 + 2 = 12
 push: *
 push: 6
 12 * 6 = 72
 push: 72
 answer: 72

 push: 100
 push: *
 push: 2
 100 * 2 = 200
 push: +
 push: 12
 200 + 12 = 212
 push: 212
 answer: 212

 push: 100
 push: /
 push: 2
 100 / 2 = 50
 push: -
 push: 25
 push: /
 push: 3
 25 / 3 = 8
 50 - 8 = 42
 push: +
 push: 85
 42 + 85 = 127
 push: 127
 answer: 127
 max@MaxGorenLaptop:~/DSA$

And that's all there is to it. If you want something a bit more... involved there is of course, the method of building an expression tree, and then walking that tree to evaluate the provided expression, but that's a discussion for another day.

 

---