Microsoft

www.microsoft.com
www.microsoft.com

## Interview Question

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

# 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.
Tags:
algorithm

0

I did 2 pass on input string.

Interview Candidate on 3 Jan 2013
0

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.

Anonymous on 7 Jan 2013
1

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

- 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;
}

Anonymous on 18 Feb 2013
0

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

NCGUY on 18 Jun 2013