Interview Question for Software Development Engineer I at Microsoft:

Jan 03, 2013

I used a different approach by making use of a queue:
- parse the string, and push in the operands and operators onto a queue
- evaluate the queue

My general approach was this:
- read in lhs, operator and rhs
- if operator is "+" or "-", enqueue lhs and operator
   > if string is empty, we are done parsing --> enqueue rhs
   > else, prepend rhs to the string (e.g. str = rhs + str), to be parsed further
- else, the operator is "*" or "/" --> perform the operation on lhs and rhs, and prepend the result to the string

Final step is evaluating the queue -- simply dequeue lhs, operator and rhs and evaluate.
 (*note: this was tricky to get right on paper, and I've made a few mistakes which I had to debug)

// Given: a well-formatted string e.g. "2 + 2*3 - 1". Evaluate the expression.
string getCurr(string& str);

int eval(string str)
{
    if (str.empty())
        return -1;

    // operand / operator queue
    std::queue<string> q;

    // construct it
    char buf[5];
    while (!str.empty())
    {
        string lhs = getCurr(str),
               oper = getCurr(str),
               rhs = getCurr(str);

        // evaluate directly
        if (oper == "*")
        {
            int res = atoi(lhs.c_str()) * atoi(rhs.c_str());

            // restore the string
            str = itoa(res, buf, 10) + str;
        }
        // evaluate directly
        else if (oper == "/")
        {
            int res = atoi(lhs.c_str()) / atoi(rhs.c_str());

            // restore the string
            str = itoa(res, buf, 10) + str;
        }
        else // "+" or "-"
        {
            q.push(lhs);
            q.push(oper);

            // finished parsing the expression
            if (str.empty())
                q.push(rhs);
            else // restore the string
                str = rhs + str;
        }
    }

    // evaluate the queue
    int res, rhs;
    string oper;

    res = atoi(q.front().c_str()); q.pop();

    while (!q.empty())
    {
        oper = q.front(); q.pop();
        rhs = atoi(q.front().c_str()); q.pop();

        if (oper == "+")
            res += rhs;
        else // "-"
            res -= rhs;
    }

    return res;
}

string getCurr(string& str)
{
    if (str.empty())
        return "";

    string curr("");
    // operator
    if (str[0] == '-' || str[0] == '+' || str[0] == '*' || str[0] == '/')
    {
        curr += str[0];
        str = str.substr(1);
    }
    else // a number
    {
        do {
            curr += str[0];
            str = str.substr(1);
        } while (!str.empty() && str[0] >= '0' && str[0] <= '9');
    }

    return curr;
}