Inchworm Evaluation, Or Evaluating Prefix-Expressions with a Queue

mgcadmin 02-25-2026

The relation between stacks and expression evaluation is well established. Stack based evaluation is employed by every computer at some level. Infix and Postfix expressions lend themselves naturally to evaluation with a stack. But what about the stacks brother, the queue? That question has been kicking around in my head for a while and every once in a while bubbles back up to the surface.

If we look to the world of theoretical computer science and automata theory, we can observe the work of Emil Post and his tag machines. Interesting and heady stuff for sure, but not quite where I'm going with this post. Instead, I want to show an algorithm that quite literally, came to me in a dream.

The Algorithm

The algorithm is for evaluating prefix expressions and works by pushing the entire expression on to a queue, operators and all, and then repeatedly dequeing  an operator which is then applied to the following terms until we reach another operator, at which point we enque the result and work on the next operator/operands. This continues until the queue contains a single item: our answer.

#include <iostream>
#include <queue>
using namespace std;
int eval(vector<string> expr);
void apply(string op, queue<string>& fq) {
    while (fq.size() > 1) {
        if (!isdigit(fq.front()[0]))
            break;
        int tmp = stoi(fq.front()); fq.pop();
        if (isdigit(fq.front()[0])) {
            switch (op[0]) {
                case '+': fq.push(to_string(tmp + stoi(fq.front()))); fq.pop(); break;
                case '*': fq.push(to_string(tmp * stoi(fq.front()))); fq.pop(); break;
                case '-': fq.push(to_string(tmp - stoi(fq.front()))); fq.pop(); break;
            }
        } else {
            fq.push(op);
            fq.push(to_string(tmp));
        }
    }
}

int eval(vector<string> expr) {
    queue<string> fq;
    for (string e : expr) {
        fq.push(e);
    }
    while (fq.size() > 1) {
        string curr = fq.front(); fq.pop();
        if (curr == "+" || curr == "*") {
            apply(curr, fq);
        } else {
            cout<<"Error: misformed expression."<<endl;
        }
    }
    return stoi(fq.front());
}

int main(int argc, char* argv[]) {
    cout<<eval({"5", "+", "1", "*", "2", "3"})<<endl;
}

---