Evaluate a simple string mathematical expression

Question

I've just taken a test for a graduate C++ developer with the question below. It didn't go too well as I couldn't decide on a clear way of completing the task. Time limit didn't help either. I'm interested in how experienced developers would have tackled the follow problem - in pseudo or sample code:

Evaluate

Write a function in C or C++ that evaluates the result of a simple expression.
The function should ignore whitespace, but stop at the first non valid character.
Valid tokens are listed in the table below:

0-9 - Only integers are allowed in expressions

() - Nested expressions should be evaluated first.

+, -, *, / - Basic operators are addition, subtraction, multiplication and division.

The expression should be parsed from left to right. It is not necessary to consider operator precedence in your solution (e.g. 1 + 3 * 4 = 16). If there is an error in the expression, the function should return false.

Suggested prototype for function:

Example:

bool evaluate(const char *expression, int &result)
{
...
}

**Input**
1+3
(1 + (12 * 2)

**Result**
4
N/A

**Return code**
true
false (missing bracket)

In addition, this is the 2nd C++ that I've failed to complete successfully. Have had 1 year intership experiece and 1 year academic experiece using C++, but I'm not prepared for some of these tests. Are there any recommended resources where I can attept to solve problems such as this one in order to gain more 'testing' experience?

Answer 1

The problem here is mostly parsing, which would be covered in a compiler course probably in second or third year. Once you can parse expressions to build up a recursive data structure representing the input (called a syntax tree) it's pretty trivial to evaluate such expressions. A recursive decent parser can also evaluate the expression as it goes without actually building a syntax tree.

For a full treatment you'd want a book on compilers, such as the dragon book. Also IIRC the book Programming: Principals and Practice using C++ covers an example like this.

You could also wait for chapter ten of The Art of Computer Programming to be published, which will cover parsing. It's scheduled to be out around 2020.

Answer 2

Here is my shortest attempt. It took about 40 minutes to type up, you can play with it on ideone (link).

The code is very straightforward, assuming that you have at least a cursory familiarity with the basic recursive descent parsing technique.

#include <iostream>
#include <cctype>
using namespace std;
bool eval_expr(const char **pe, int &lhs, bool inside = false);
// gets the next char after skipping optional whitespace
char skip_ws(const char **pe) {
    while (**pe == ' ') ++(*pe);
    return **pe;
}
// evaluates a parenthesized expression or a number
bool eval_prim(const char **pe, int &res) {
    char c = skip_ws(pe);
    if (c == '(') {
        ++(*pe);
        if (!eval_expr(pe, res, true)) return false;
        ++(*pe);
        return true;
    }
    if (isdigit(c)) {
        res = 0;
        while (isdigit(c)) {
            res = 10*res + c - '0';
            c = *(++(*pe));
        }
        return true;
    }
    return false;
}
// evaluates a chain of + - * / operations
bool eval_expr(const char **pe, int &lhs, bool inside) {
    if (!eval_prim(pe, lhs)) return false;
    char op;
    while ((op = skip_ws(pe)) && (op == '+' || op == '-' || op == '*' || op == '/')) {
        ++(*pe);
        int rhs;
        if (!eval_prim(pe, rhs)) return false;
        switch (op) {
            case '+': lhs += rhs; break;
            case '-': lhs -= rhs; break;
            case '*': lhs *= rhs; break;
            case '/': lhs /= rhs; break;
        }
    }
    return inside ? op == ')' : !op;
}
// wrapper API to hide an extra level of indirection
bool evaluate(const char *e, int &result) {
    return eval_expr(&e, result);
}

Answer 3

This is a simple scan push apply (the twist is the braces).

1. Look for a number:
   • If you see a number push onto stack
   • if you see a '(' push it onto stack and goto 1
   • Otherwise an error.
2. Look for an op:
   • If you see an op push it onto stack
   • Otherwise an error
3. Look for a number:
   • If you see a number push onto stack
   • If you see a '(' push onto stack and goto 1
   • Otherwise an error
4. pop last three items from the stack (should be number op number)
   
   • do the operation and push the result onto the stack.
5. Now the complex bit:
   • Peek to see if the next character is a ')' if it is goto "PopCode" below.
6. If no more input goto 7.
   • Otherewise goto 2
7. If only one item on the stack you have your result.
   • Otherwise an error.

PopCode

1. Pop last two values from the stack. Should be '( Number'
   • If it is not then an error
2. Throw away the '('
3. If the top of the stack is an op push value goto 4 (above)
4. Otherwise push the value onto the stack goto 5 (above)

When finished there should be one number on the stack.

Example:

1+3
Rule 1: push 1             stack = '1'
Rule 2: push +             stack = '1 +'
Rule 3: push 3             stack = '1 + 3'
Rule 4: pop and do:        stack = '4'
Rule 5: Nothing            stack = '4'
Rule 6: goto 7             stack = '4'
Rule 7:                    stack = '4'

(1 + (12 * 2)
Rule 1: push ( goto 1      stack = '('
Rule 1: push 1             stack = '( 1'
Rule 2: push +             stack = '( 1 +'
Rule 3: push ( goto 1      stack = '( 1 + ('
Rule 1: push 12            stack = '( 1 + ( 12'
Rule 2: push *             stack = '( 1 + ( 12 *'
Rule 3: push 2             stack = '( 1 + ( 12 * 2'
Rule 4: Pop and do:        stack = '( 1 + ( 24'
Rule 5: Do 'PopCode'       stack = '( 1 + ( 24'
Pop  1: Pop 2              stack = '( 1 +'
Pop  2: Holding 24         stack = '( 1 +'
Pop  3: push 24 goto 4     stack = '( 1 + 24'
Rule 4: Pop and do         stack = '( 25'
Rule 5: Nothing            stack = '( 25'
Rule 6: goto 7             stacj = '( 25'
Rule 7: More than 1 item error

Re-Doing with correct formula
(1 + (12 * 2))
Rule 1: push ( goto 1      stack = '('
Rule 1: push 1             stack = '( 1'
Rule 2: push +             stack = '( 1 +'
Rule 3: push ( goto 1      stack = '( 1 + ('
Rule 1: push 12            stack = '( 1 + ( 12'
Rule 2: push *             stack = '( 1 + ( 12 *'
Rule 3: push 2             stack = '( 1 + ( 12 * 2'
Rule 4: Pop and do:        stack = '( 1 + ( 24'
Rule 5: Do 'PopCode'       stack = '( 1 + ( 24'
Pop  1: Pop 2              stack = '( 1 +'
Pop  2: Holding 24         stack = '( 1 +'
Pop  3: push 24 goto 4     stack = '( 1 + 24'
Rule 4: Pop and do         stack = '( 25'
Rule 5: Do 'PopCode'       stack = '( 25'
Pop  1: Pop 2              stack = ''
Pop  2: holding 25         stack = ''
Pop  3: Nothing.           stack = ''
Pop  4: push 25 goto 5     stack = '25'
Rule 5: Nothing            stack = '25'
Rule 6: goto 7             stack = '25'
Rule 7: Result = 25

Answer 4

Begin with a simple grammar:

expr: n-expr {o-expr} | p-expr {o-expr}
n-expr: [0-9]n-expr
p-expr: ( expr )
o-expr: op expr
op: + | - | * | /

This is probably the largest hurdle for the question. You want to be able to write a simple top down recursive descent parser, so your grammar needs to be written in a way to allow that to happen.

Then, the implementation from there is fairly straightforward:

bool expr (const char *&s, int &result, int eos = 0) {
    while (isspace(*s)) ++s;
    if (*s == eos) return false;
    if (isdigit(*s)) {
        if (!n_expr(s, result)) return false;
    } else if (*s == '(') {
        if (!p_expr(s, result)) return false;
    } else return false;
    while (isspace(*s)) ++s;
    if (*s == eos) return true;
    return o_expr(s, result, eos);
}

bool n_expr (const char *&s, int &result) {
    int n = 0;
    while (isdigit(*s)) n = 10 * n + (*s++ - '0');
    result = n;
    return true;
}

bool p_expr (const char *&s, int &result) {
    if (expr(++s, result, ')')) {
        ++s;
        return true;
    }
    return false;
}

bool o_expr (const char *&s, int &result, int eos) {
    int oresult = 0;
    const char *op = strchr("+-*/", *s);
    if (op == 0) return false;
    if (!expr(++s, oresult, eos)) return false;
    switch (*op) {
    case '+': result += oresult; break;
    case '-': result -= oresult; break;
    case '*': result *= oresult; break;
    case '/': result /= oresult; break;
    default: return false;
    }
    return true;
}

Answer 5

The easiest way to solve a (not necessarily) simple mathematical expression is to use the Shunting Yard algorithm to convert it to Reverse Polish Notation, which is almost trivial to parse using a stack. Of course it might not be feasible to do so for an assignment or an interview (perhaps unless a SY algorithm reference is available).