Pub

Classical Solutions To Expression Evaluation Problems

By: Homecox. 12/11/2013

The problem of expression evaluation is a basic one in compiler theory. It usually consists of several basic operators (+, -, *, /, ^) operating on integers, and may involve the use of parenthesis.

Here we discuss several variations of this type of problems and corresponding classical solution(s). The solutions are not unique, but we just introduce some classical ones here. By classical, we mean not "Ad Hoc" methods, but based on solid theory and sound practice.

Problem I: Validate an expression consists of integers 0-9, +/- and parentheses. E.g., 3+(4-(5-(4)). Assume no space in between the characters.

Solution: This is a most basic expression parsing problem. The grammar for this can be written as:

E = F + E | F - E | F
F = (E) | n
n = 0 | [1-9][0-9]*

The formula here can be translated directly into functions. This is recursive descent parsing. The solution is shown below.

If we want to evalute the value of such an expression, we can just replace return type of functions num(), E() and F() from bool to integer.

bool is_num(const char c) {
    return c >= '0' && c <= '9';
}

bool num(const char*& p) {
    if (*p == '0') {
        ++ p;
        return ! is_num(*p); // a number does not start with 0.
    }
    else if (is_num(*p)) {
        while (is_num(*p)) { ++ p; }
        return true;
    }
    return false;
}

bool E(const char *& p);

bool F(const char *& p) {
    if (*p == '(') {
        ++ p;
        if (! E(p)) return false;
        if (*p == ')') { ++ p; return true; }
        else return false;
    }
    else if (is_num(*p)) {
        return num(p);
    }
    return false;
}

bool E(const char *& p) {
    if (! F(p)) return false;
    
    while (*p == '+' || *p == '-') {
        ++ p;
        if (! E(p)) return false;
    }
    return true;
}

bool validate(const string& expr) {
    int len = expr.size();
    const char * p = expr.c_str();
    return E(p) && *p == '\0';
}

Problem II: An expression consists of integers, and operators +, -, *. Evaluate its value. E.g., 3+4*5-6. Assume no space in between characters, and the expression is always correct.

Soultion: A solution is to use a value stack for numbers (sn). Whenever the new operator is *, apply the operation, otherwise keep adding new number to the stack (if operator is -, add negative value of the new number). In the end, add up all values in the value stack.

It is easy to see that, if the divide operator / is used, simply use double as the data type for the stack, and add one more row "else if (op == '/') { sn.top() /= num; }" below the line to process '*' should work.

Note that this solution is the simplified version of the 2-stack algorithm to parse infix math expressions. The 2-stack algorithm is called the shunting-yard algorithm, and was invented by Edsger Dijkstra. The shunting-yard algorithm can be used to generate output in Reverse Polish Notation (RPN) or Abstract Syntax Tree (AST).

int getNum(const char * &s) {
    int num = 0;   
    while (*s >= '0' && *s <= '9') {
        num = num * 10 + (*s ++ - '0');
    }
    return num;
}

int evaluate(const string& expr) {
    stack<int> sn;
    const char * s = expr.c_str();
          
    sn.push(getNum(s));
    
    while (*s) {
        char op = *s ++;        
        int num = getNum(s);
        
        if (op == '*') { sn.top() *= num; }
        else if (op == '-') { sn.push(- num); }
        else { sn.push(num); }
    }
    
    int v = 0;
    while(!sn.empty()) {
        v += sn.top();
        sn.pop();
    }
    
    return v;
}

Problem III: Evaluate a proper expression consisting of float numbers (can be positive or negative), operators +, -, *, / , ^ and parentheses (, ).

Solution A: Here we build a expression parse tree (an Abstract Syntaxt Tree or AST) and then evaluate it. Precedence is used: + and - has the lowest precedence, then * and /, ^ has higher precedence, and whenever ( and ) are used, precedence is incremented by one. This idea can extend to more operators such that it extends to a full functional calculator.

The idea is whenever a subexpression has higher precedence, we insert it as a subtree of the current node. This is operator precedence parsing. Alternative to operator precedence parsing, of course, is to use grammar-directed recursive descent parsing, as in the first problem above.

The entire code is below. Note that the central part of the algorithm is function buildAST(), which is short, only about 30 LOC, and can keep this size when extended to more operators.

Function getNextToken() handles the task of parsing out the next token as either a number of operator, and increment precedence level when '(' is found, with error checking capability. Function getNextToken() can shortened for simpler number requirement.

The constructed parse tree can be easily converted into postfix notation. Evaluation is done with the eval() function easily.

// This builds an parse tree for the expression and evaluate it.
// to improve:
// - allow number to have multiple digits. 
// - allow neg number: (done, allow +/- before a number) 
// - allow number to be of format: .3 -> 0.3 
// - allow parenthesis '()'. 
// - check for invalid input - not: operand [operator, operand]+. 
// - allow '^' for power operation. 

struct Node {
    double val;
    char op;
    int op_prec; // precedence of operator
    int type; // 0 - operand, 1 - operator
    Node * left;
    Node * right;
    Node(double _val, char _op, int _type) : 
         val(_val), op(_op), type(_type), left(NULL), right(NULL) {}
};

class Evaluator {
private:
    int prec_base;
    const char * p0; // record start position of input string.
    
    void err(char * msg, const char * p) {
        printf("input error: %s, at input position %d\n", msg, p - p0);
        printf("%s\n", p0);
        for (int i = 0, len = p - p0; i < len; ++ i) putchar(' ');
        printf("^\n");
        exit(1);
    }

    void dump_node(Node * n) {
        if (n->type == 0) printf(" %.1lf ", n->val);
        else printf(" %c ", n->op);
    }
    
    void dump(Node * n) {
        if (! n) return;
        if (! n->left && ! n->right) {
            dump_node(n); 
            return;
        }
        
        printf("(");
        dump(n->left);
        dump_node(n); 
        dump(n->right);
        printf(")");
    }
    
    // get precedence.
    int prec(char op) {
        if (op == '+' || op == '-') return 1;
        if (op == '*' || op == '/') return 2;
        if (op == '^') return 3;
        return 0;
    }
    
    // get type: operand or operator.
    int isOp(char c) { 
        return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^'); 
    }
    
    int isDigit(char c) { return c >= '0' && c <= '9'; }
    
    // type - desired type of new token.
    Node * getNextToken(const char *& input, int type) {
        const int prec_base_inc = 4; // 1 + max(op prec)
        while (isspace(*input)) ++ input; // skips spaces.
        
        if (! *input) return NULL; // end of input.

        while (*input == '(') {
            prec_base += prec_base_inc;
            ++ input;
        }
        
        // check if is desired type.
        if (! ((type == 1 && isOp(*input) ) ||
               (type == 0 && (isDigit(*input) || *input == '+' || 
                              *input== '-' || *input=='.'))) ) {
            err("wrong type of operand/operator", input);
        }
        
        Node * n;        
        if (type == 1) { // operator.
            n = new Node(0, *input, type); 
            n->op_prec = prec(n->op) + prec_base;
            ++ input;
        }
        else { // type == 0: operand.
            double val;
            // note: sscanf requires no space between sign and value.
            sscanf(input, "%lf", &val);
            n = new Node(val, 0, type);
            if (*input == '+' || *input == '-') ++ input;
            if (! (isDigit(*input) || *input == '.')) {
                err("incomplete number", input);
            }
            
            bool dot_used = false; // allow only one dot.
            while ( isDigit(*input) || (*input == '.' && !dot_used)) {
                  if (*input == '.') dot_used = true;
                  ++ input;
            }
            
            while (*input == ')') {
                prec_base -= prec_base_inc;
                ++ input;
            }
        }
        
        return n;
    }
    
    void buildAST(const char * input, Node *& root) {
        root = getNextToken(input, 0);
        
        while (1) {
            Node * opt = getNextToken(input, 1);         
            if (! opt) return; // end of input.
            
            Node * opd = getNextToken(input, 0); 
            
            if (root->type == 0 || opt->op_prec <= root->op_prec) {
                opt->left = root;
                opt->right = opd;
                root = opt;
            } else {
                // insert opt above the operand node, or the first 
                // operator node x where opt.prec <= x.prec.
                Node * n = root;
                while (1) {
                    if (n->right->type == 0 || 
                            opt->op_prec <= n->right->op_prec) {
                        opt->left = n->right;
                        opt->right = opd;
                        n->right = opt;
                        break;
                    } else {
                        n = n->right;
                    }
                } // end of while
            } // end of if   
        } // end of while
    }
    
    double eval(Node * t) {
        if (! t) return 0;
        if (t->type == 0) return t->val; // t is operand.
        
        // t is operator.
        if (t->op == '+') return eval(t->left) + eval(t->right);
        if (t->op == '-') return eval(t->left) - eval(t->right);
        if (t->op == '*') return eval(t->left) * eval(t->right);
        if (t->op == '/') return eval(t->left) / eval(t->right);
        if (t->op == '^') return pow(eval(t->left), eval(t->right));
    }
    
public:
    Evaluator() { prec_base = 0; }
    ~Evaluator() { /* destroy AST. */ } 
    
    double calc(const char * s) {
        p0 = s; // record start pointer position.
        
        Node * p = NULL;
        buildAST(s, p);
        dump(p); puts("");
        
        return eval(p);
    }
};

Solution B: This can also be solved using the 2-stack shunting-yard algorithm. Some discussions can be found here or here.

The implementation of the 2-stack shunting-yard algorithm is below. The key function is eval(). A inner while loop is used, since the input string may contain something like a+b*(c+d)*e, so continous reduction upon '*' may be needed. Also note the handling of the precedence of '(' and ')': here its precedence is always 0, but in solution A its precedence is always 1 plus current precedence.

The basic difference between soluations A and B, is that in solution A we create a subtree for an operation of higher precedence, but in solution B we immediately calculate the result of such an operation. That is the single only significant difference. It is easy to extend from B to A, which is to extend the shunting-yard algorithm to use AST as output.

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

int getNum(const char * &s) {
    int num = 0;   
    while (*s >= '0' && *s <= '9') {
        num = num * 10 + (*s ++ - '0');
    }
    return num;
}

int prec(char c) {
    if (c == '(' || c == ')') return 0;
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    if (c == '^') return 3;
    // else, error.
    return -1;
}

double calc(double a, double b, char op) {
    if (op == '+') return a + b;
    else if (op == '-') return a - b;
    else if (op == '*') return a * b;
    else if (op == '/') {
        if (abs(b) < 0.0000001) return INT_MAX; // divide by zero error
        else return a / b;
    }
    else if (op == '^') return pow(a, b);
    else return INT_MAX; // error
}

bool is_op(char c) {
    return c == '+' || c == '-' || c == '*' || 
           c == '/' || c == '(' || c == ')';
}

double eval(string expr) {
    stack<double> s;
    stack<char> sop;    
    const char * p = expr.c_str();
    
    while (*p == '(') sop.push(*p ++);
    s.push(getNum(p));
    
    while (*p) {
        while (is_op(*p)) sop.push(*p ++); 
        if (*p) s.push(getNum(p)); 
        
        while (1) {
            char op = sop.top();
            sop.pop();
            
            if (sop.empty()) { 
                sop.push(op); 
                break; 
            }
            else if (sop.top() == '(' && op == ')') { 
                sop.pop(); 
            }
            else if (prec(op) > prec(sop.top())) {
                double b = s.top(); s.pop();
                double a = s.top(); s.pop();
                s.push( calc(a, b, op) );
            }
            else {
                sop.push(op);
                break;
            }
        }
    }
    
    while (! sop.empty()) {
        double b = s.top(); s.pop();
        double a = s.top(); s.pop();
        char op = sop.top(); sop.pop();
        double v = calc(a, b, op);
        s.push(v);
    }
    
    return s.top();
}

void test(string s, double v) {
    double a = eval(s);    
    cout << s << " = " << eval(s) << 
         (abs(a - v) < 0.0000001) ? " .....ok" : " .....errrrrr") << endl;
}

int main() {
    test("1", 1);
    test("1+2", 3);
    test("1+2*3", 7);
    test("1+3/2", 2.5);
    test("1+2*(3+4)", 15);
    test("1+2*(3+4)/2", 8);
    test("1+2*(3+4)/2*3", 22);
    test("1+2*(3+4)/2*3/10", 3.1);
    test("1+2*(3+4)/2*3/10+(5-6)", 2.1);
    test("1+2*(3+4)/2*3/10+(5-6)*(4-3)", 2.1);
    return 0;
}

Summary

To summarize, evaluation of math expressions can be solved using recursive descent parsing based on grammar, shunting-yard algorithm based on 2 stacks (invented by Edsger Dijkstra), or operator precedence parsing. In fact, operator precedence is a generalization of the shunting-yard algorithm.

As a last note, all the 3 problems here can be solved using the 2-stack shunting-yard algorithm.

References: