CareerCup

I have to assume the person who posted this misunderstood the question and the input char* was already in postfix form. If not then this partially explains why microsoft has trouble hiring SDETs.

Infix to postfix (Shunting-yard algorithm) and then evaluate the postfix expression.

Evaluating postfix isn't that much code, but the code to convert infix to postfix is a lot of code. Did the interviewer expect you to code a complete solution to both problems while on the phone with him/her?

If we do two separate scans, one for the * and / and then the other for the + and - . in the first scan all the * and / signs will be removed and the adjacent numbers will be multiplied or divided. then in the second scan we will do the addition and the subtraction.

I think that since the case is so simple (no parenthesis, just the four basic operators that all have left precedence) the problem can be simply solved by left to right parsing the string with two loops : The outer loop handles addition and substraction while the inner loop handles multiplication and division. The solution is quite simple actually...

That being said, I doubt I could solve that over the phone...

I think we can solve this question by using a stack. When there is a + or - operation we push the numbers to a stack and when there is a * or / operation we first handle the operation(pop the lat number and) then push the new number(operation with the new comer and the popped number) to the stack. At the end we add all the numbers in the stack. But there is an important point that when there is a - sign we need to push the number after multiplying it by -1.

<pre lang="c++" line="1" title="CodeMonkey22804" class="run-this">#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <iterator>
#include <stack>

using namespace std;
template<typename RT, typename T, typename Trait, typename Alloc>
RT ss_atoi( const std::basic_string<T, Trait, Alloc>& the_string )
{
std::basic_istringstream< T, Trait, Alloc> temp_ss(the_string);
RT num;
temp_ss >> num;
return num;
}

enum PRECEDENCE
{
None = 11,
Unary = 10,
Power = 9,
Times = 8,
Div = 7,
IntDiv = 6,
Modulus = 5,
Plus = 4,
};

struct ExpressionNode
{
ExpressionNode *leftChild, *rightChild;
string Expression;
char Op;

public:
ExpressionNode(string newExpr)
{
leftChild = NULL;
rightChild = NULL;
Expression = newExpr;
Op = NULL;
ParseExpression();
}

void ParseExpression();
float Evaluate();
};


void ExpressionNode::ParseExpression()
{
if (!Expression.length() == 0)
{
// if 1st thing is + or - then its unary
bool is_unary = true;

PRECEDENCE best_prec = None;

// Find the operator with the lowest precedence.
// Look for places where there are no open parenthesis
int open_parens = 0;
int best_i = -1;
for (unsigned int i = 0; i < Expression.length(); ++i)
{
// Assume we will not find an operator. In that case the next operator
// will not be unary.
bool next_unary = false;

// Examine the next character
char ch = Expression[i];

if (ch == ' ')
{
// Skip the whitespaces.
}
else if (ch == '(')
{
// Increment the parens count
open_parens += 1;
// A + or - after "(" is unary
next_unary = true;
}
else if (ch == ')')
{
// Decrement the paren count
open_parens -= 1;
// An operator after ')' is not unary
next_unary = false;
// if paren_count < 0, too many //)'s
if (open_parens < 0)
cout << "Parse Error. Too many )s in expression '" << endl;
}
else if (open_parens == 0)
{
// we have no open parens. See if its an operator
if (ch == '^' || ch == '*' ||
ch == '/' || ch == '\\' ||
ch == '%' || ch == '+' ||
ch == '-')
{
// An operator after an operator is unary
next_unary = true;

// See if this operator has higher precedence than the current one
switch(ch)
{
case '^':
if (best_prec >= Power)
{
best_prec = Power;
best_i = i;
}
break;
case '*':
case '/':
if (best_prec >= Times)
{
best_prec = Times;
best_i = i;
}
break;
case '\\':
if (best_prec >= IntDiv)
{
best_prec = IntDiv;
best_i = i;
}
break;
case '%':
if (best_prec >= Modulus)
{
best_prec = Modulus;
best_i = i;
}
break;
case '+':
case '-':
if (!is_unary && best_prec >= Plus)
{
best_prec = Plus;
best_i = i;
}
break;
}
}
}

is_unary = next_unary;
}
// Make sure the open paren count is zero
if (open_parens != 0)
cout << "Parse Error" << endl;

// See if we have an operator
if (best_prec < None)
{
string lexpr = Expression.substr(0, best_i);
string rexpr = Expression.substr(best_i+1);
Op = Expression[best_i];

leftChild = new ExpressionNode(lexpr);
rightChild = new ExpressionNode(rexpr);
return;
}

// We don't have an operator yet.
// There are several possibilities:
//
// 2. Expression is -expr2 or +expr2 for some expr2.
// 4. Expression is a literal like "3.14159".

// Look for -expr2.
if (Expression.compare(0, 1, "-", 1) == 0)
{
Op = '-';
leftChild = new ExpressionNode(Expression.substr(1, Expression.length() - 1));
return;
}

// Look for +expr2.
if (Expression.compare(0, 1, "+", 1) == 0)
{
Op = '+';
leftChild = new ExpressionNode(Expression.substr(1, Expression.length() - 1));
return;
}

// It must be a literal such as "2.71828".
return;
}
}

float ExpressionNode::Evaluate()
{
// See if we have an operand.
if (Op == NULL)
{
// No operand. This is a literal.
return ss_atoi<float>(Expression);
}
else
{
// See what the operand is.
switch (Op)
{
case '^': // Power.
return pow(leftChild->Evaluate(), rightChild->Evaluate());
case '*': // Times.
return leftChild->Evaluate() * rightChild->Evaluate();
case '/': // Divide.
return leftChild->Evaluate() / rightChild->Evaluate();
case '\\': // Integer divide.
return (int)(leftChild->Evaluate() / rightChild->Evaluate());
case '%': // Modulus.
return (int)(leftChild->Evaluate()) % (int)(rightChild->Evaluate());
case '+': // Plus or unary plus.
if (rightChild == NULL)
{
// Unary +.
return +leftChild->Evaluate();
}
else
{
// Binary +.
return leftChild->Evaluate() + rightChild->Evaluate();
}
case '-': // Minus or unary minus.
if (rightChild == NULL)
{
// Unary -.
return -leftChild->Evaluate();
}
else
{
// Binary -.
return leftChild->Evaluate() - rightChild->Evaluate();
}
default:
cout << "Evaluate error. Unknown function '" << endl;
} // switch (Op.ToLower())
}
} // Evaluate()

int main()
{
//string expression = "4-5*8+4/2";
float result = 0.0f;
string expression;
cout << "Enter Expression: ";
cin >> expression;
ExpressionNode* m_ExpressionTree = new ExpressionNode(expression);
result = m_ExpressionTree->Evaluate();
cout << "Result of Expression: " << expression << endl;
cout << result << endl;
return 0;
}
</pre><pre title="CodeMonkey22804" input="yes">4-5*8+4/2</pre>

I like the idea of doing 4 passes and then evaluating *,/,+,- in order

Much easier to do it recursively. Recursion will take care of the stack. Split by +/- first for each sub expression, and when no more +/- do the *and division. It is less than 10 lines of code probably.

stop pasting bunch of codes! Algos r better!

@ crac nice solution...

my solution

float evaluate(char* s)
{
char* st_no = s;
char* cur = s;

int res_type = 0; // 0:add, 1:subtract
int inner_res_type = -1; // 0:mult, 1:div

float res = 0;
float inner_res;

char buf[5];

while(1)
{
	bool end = false;

	if(*cur == '+' || *cur == '-'
		|| *cur == '*' || *cur == '/' || *cur == 0)
	{

		int t_res_type = res_type;
		int t_inner_res_type = inner_res_type;

		inner_res_type = -1;

		if(*cur == '+')		res_type = 0;
		else if(*cur == '-')	res_type = 1;
		else if(*cur == '*')	inner_res_type = 0;
		else if(*cur == '/')	inner_res_type = 1;
		else			end = true;

		int x=0;
		while(st_no != cur)
			buf[x++] = *(st_no++);
		buf[x] = 0;
		int val = atoi(buf);
		if(!end)
			st_no = cur + 1;

		if(t_inner_res_type == 0)
			inner_res *= val;
		else if(t_inner_res_type == 1)
			inner_res /= val;
		else
			inner_res = val;

		if(inner_res_type == -1)
		{
			if(t_res_type == 0)
				res += inner_res;
			else
				res -= inner_res;
		}
	}

	if(end)
		break;
	cur++;
}
return res;
}

I think the examinator just checked whether one read Stroustrup's books on C++ or not. There is a full algorithm he has in his books on it.

double ParseAtom(char*& expr) {
// Read the number from string
char* end_ptr;
double res = strtod(expr, &end_ptr);
// Advance the pointer and return the result
expr = end_ptr;
return res;
}

// Parse multiplication and division
double ParseFactors(char*& expr) {
double num1 = ParseAtom(expr);
for(;;) {
// Save the operation
char op = *expr;
if(op != '/' && op != '*')
return num1;
expr++;
double num2 = ParseAtom(expr);
// Perform the saved operation
if(op == '/')
num1 /= num2;
else
num1 *= num2;
}
}

// Parse addition and subtraction
double ParseSummands(char*& expr) {
double num1 = ParseFactors(expr);
for(;;) {
char op = *expr;
if(op != '-' && op != '+')
return num1;
expr++;
double num2 = ParseFactors(expr);
if(op == '-')
num1 -= num2;
else
num1 += num2;
}
}

double EvaluateTheExpression(char* expr) {
return ParseSummands(expr);
};

How about handling the decimal point? we will have to convert stream of chars to a float, i don't think anyone has handled that???