## Interview Question

Software Development Engineer I Interview*(Student Candidate)* Redmond, WA

`Microsoft`

Answer## Given a string of format '2+3*2-1', calculate and return

the result. No parenthesis in the input, just integers and + - * / operators. Operator precedence has to be considered. Linear time complexity and minimal data structure use is preferred.

## Interview Answer

4 Answers

I also did two passes on the input string. I created the following helper classes:

Calculate, which takes in the input string, the location of the operation and the operation itself, and returns the result of the calculation. It's not too hard to figure out how to extract the operands from the string (just iterate backwards/forwards until you bump into the end, beginning or another operator).

InsertResultInStr, which takes in the input string, the location of insertion and places a given integer into the input string. I couldn't prove this, but I think its true that the result of a multiplication between m and n digit numbers can always fit in the concatenation of those numbers with '*' in the middle. Sorry if the explanation is a little confusing, but InsertResultInStr(input, 3, 6) for input string = "2 + 3*2* - 1" should result in string = "2 + 6 - 1".

Now, in the main fn, iterate through the string until we find a '*' or a '/', and when we do, calculate the answer via Calculate(), then InsertResultInStr(). Then iterate through the string again looking for '+' and '-', and finally convert the final string to an int and return it.

One thing that is not clear in the description is what we should do to handle if a/b is not an int. My guess is that a/b will always return an integer. I guess you can handle this in any way you want: ignore the stuff after the decimal point, or maybe keep the maximum amount of precision that your string-space can handle.

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;

}

Use 2 stacks. one for operands and one for operators. Keep pushing in operator as long as the newly pushed opertor has higher precedence than the "top of stack " operator. if not, pop out 2 operands and calculate result and again push it on stack

## Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up

I did 2 pass on input string.

Jan 3, 2013