Interview Question Software Engineer / Developers
Country: United States
#test.py
def is_num( c ):
if '0'<=c and c<='9' :
return True
else:
return False
def Eval():
while True:
str = raw_input("Enter your algebraic expression: " )
ope = []
num = []
len1 = len( str )
tmp = 0
for i in range( len1 ):
if is_num( str[i] ) :
tmp = tmp * 10 + (int)(str[i])
else :
while len(ope) > 0 and ( ope[-1]=='*' or ope[-1]=='/' ):
if ope[-1] == '*' :
tmp = num[-1] * tmp
else :
tmp = (float)(num[-1]) / tmp
del ope[-1]
del num[-1]
num.append( tmp )
tmp = 0
ope.append( str[i] )
while len(ope) > 0 and ( ope[-1]=='*' or ope[-1]=='/' ):
if ope[-1] == '*' :
tmp = num[-1] * tmp
else :
tmp = (float)(num[-1]) / tmp
del ope[-1]
del num[-1]
while len(ope) > 0 and ( ope[-1]=='+' or ope[-1]=='-' ):
if ope[-1] == '+' :
tmp = num[-1] + tmp
else :
tmp = num[-1] - tmp
del ope[-1]
del num[-1]
print "Value is: ",tmp
if __name__ == '__main__':
Eval()
Parse the expression to generate a binary tree, which has values as leaf, then eval the tree:
#include <list>
#include <iostream>
#include <cassert>
class CNode
{
CNode * parent_;
CNode * left_;
CNode * right_;
double val_;
char type_;
public:
explicit CNode(char t):parent_(NULL),left_(NULL),right_(NULL),val_(0),type_(t){}
explicit CNode(double v):parent_(NULL),left_(NULL),right_(NULL),val_(v),type_(0){}
bool hasParent() const{return (NULL != parent_);}
CNode * parent() const{return parent_;}
void setRight(CNode & n){
right_ = &n;
n.parent_ = this;
}
void setLeft(CNode & n){
left_ = &n;
n.parent_ = this;
}
bool isNumber() const{return (0 == type_);}
bool isAddMinus() const{return ('+' == type_ || '-' == type_);}
bool isMulDiv() const{return ('*' == type_ || '/' == type_);}
double calc() const{
if(isNumber())
return val_;
assert(left_ && right_);
switch(type_){
case '+':return (left_->calc() + right_->calc());
case '-':return (left_->calc() - right_->calc());
case '*':return (left_->calc() * right_->calc());
case '/':return (left_->calc() / right_->calc());
default:;
}
assert(false);
return 0;
}
};
typedef std::list<CNode> __Nodes;
const char * parseToken(const char * p, __Nodes & nodes)
{
assert(p);
if('+' == *p || '-' == *p || '*' == *p || '/' == *p){
nodes.push_back(CNode(*p++));
return p;
}else if('0' <= *p && *p <= '9'){
double v = 0;
do{
v = v * 10 + *p - '0';
++p;
}while('0' <= *p && *p <= '9');
nodes.push_back(CNode(v));
return p;
}
return NULL;
}
CNode & findHead(CNode & n)
{
CNode * p = &n;
for(;p->hasParent();p = p->parent());
return *p;
}
const CNode & findHead(const CNode & n)
{
const CNode * p = &n;
for(;p->hasParent();p = p->parent());
return *p;
}
CNode & findSubHead(CNode & n)
{
CNode * p = &n;
while(p->hasParent()){
CNode * pp = p->parent();
if(!pp->isMulDiv())
break;
p = pp;
}
return *p;
}
void adjustNodes(CNode & last, CNode & cur)
{
if(last.isNumber()){
if(cur.isAddMinus()){
cur.setLeft(findHead(last));
return;
}else if(cur.isMulDiv()){
CNode & h = findSubHead(last);
CNode * p = h.parent();
if(p)
p->setRight(cur);
cur.setLeft(h);
return;
}
}else{
if(cur.isNumber()){
last.setRight(cur);
return;
}
}
assert(false);
}
bool buildTree(__Nodes & nodes)
{
if(nodes.size() < 2)
return true;
__Nodes::reverse_iterator i = nodes.rbegin();
CNode & cur = *i++;
CNode & last = *i;
if(cur.isNumber() == last.isNumber())
return false;
adjustNodes(last, cur);
return true;
}
bool parseExpr(const char * expr, __Nodes & nodes)
{
assert(expr);
for(const char * p = expr;*p;){
if(NULL == (p = parseToken(p, nodes)))
return false;
if(!buildTree(nodes))
return false;
}
if(nodes.empty() || !nodes.back().isNumber())
return false;
return true;
}
double calcTree(const __Nodes & nodes)
{
if(nodes.empty())
return 0;
const CNode & h = findHead(nodes.front());
return h.calc();
}
double eval(const char * expr)
{
__Nodes nodes;
if(parseExpr(expr, nodes))
return calcTree(nodes);
return 0; //error format expr
}
int main()
{
std::cout<<eval("2+5/2")<<"\n"; //4.5
std::cout<<eval("12*2+5/2-3")<<"\n";//23.5
}
Java solution. (No parenthesis supported, integer calculation. Can be easily expanded.)
public String evaluate(String string) {
string = process(string, "(\\d+)([\\*\\/])(\\d+)");
string = process(string, "(\\d+)([\\+\\-])(\\d+)");
return string;
}
private String process(String string, String pattern) {
Matcher m = Pattern.compile(pattern).matcher(string);
StringBuffer buf = new StringBuffer();
while (m.find()) {
m.appendReplacement(buf, evaluate(m.group(1), m.group(2), m.group(3)));
}
m.appendTail(buf);
return buf.toString();
}
private String evaluate(String o1, String op, String o2) {
int i1 = Integer.parseInt(o1);
int i2 = Integer.parseInt(o2);
int ret;
switch (op) {
case "*" :
ret = i1 * i2;
break;
case "-" :
ret = i1 - i2;
break;
case "+" :
ret = i1 + i2;
break;
case "/" :
ret = i1 / i2;
break;
default: throw new IllegalArgumentException("invalid operator");
}
return Integer.toString(ret);
}
I screwed up the middle:
private String process(String string, String spattern) {
Pattern pattern = Pattern.compile(spattern);
Matcher m = pattern.matcher(string);
while (m.find()) {
StringBuffer buf = new StringBuffer();
m.appendReplacement(buf, evaluate(m.group(1), m.group(2), m.group(3)));
m.appendTail(buf);
string = buf.toString();
m = pattern.matcher(string);
}
return string;
}
Parenthesis processing:
public String evaluate(String string) {
string = process(string, "(\\d+)([\\*\\/])(\\d+)");
string = process(string, "(\\d+)([\\+\\-])(\\d+)");
while (true) {
String rep = string.replaceAll("\\((\\d+)\\)", "$1");
if (rep.equals(string)) {
break; // no resolvable parenthesis found
}
string = evaluate(rep);
}
return string;
}
package MyInterview;
- Anonymous December 19, 2013import java.util.*;
public class EvaluateExpression {
private String expres;
private Stack st=new Stack();
private int eval(int op1,char op,int op2)
{ int result=0;
if(op=='+') result= op1+op2;
else if(op=='-') result= op1-op2;
else if(op=='*') result=op1*op2;
else if(op=='/') result=op1/op2;
return result;
}
public void evaluate(String s)
{ int op1=0;
int op2=0;
char op='+';
for(int i=0;i<s.length();i++)
{
if(s.charAt(i) !=')')
st.push(s.charAt(i));
else
{
while((char)st.peek()!='(')
{
op2=(int)st.pop();
op=(char)st.pop();
op1=(int)st.pop();
if((char)st.peek()=='(') break;
st.push(eval(op1,op,op2));
}
st.pop();
st.push(eval(op1,op,op2));
}
}
System.out.println(st);
while(st.size()!=1)
{
op2=(int)st.pop();
op=(char)st.pop();
op1=(int)st.pop();
st.push(eval(op1,op,op2));
System.out.println(st);
}
System.out.println((int)st.peek());
}
public static void main(String[] args) {
// TODO Auto-generated method stub
EvaluateExpression ee=new EvaluateExpression();
ee.evaluate("2+4/2");
}
}