Facebook Interview Question
SDE1sCountry: United States
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Exp {
public:
Exp(char op)
{
op_ = op;
new_operand_ = true;
}
void GrowOperands(char c)
{
if (c == ' ') {
new_operand_ = true;
} else {
if (new_operand_) {
new_operand_ = false;
operands_.push_back(0);
}
operands_.back() = operands_.back() * 10 + (c - '0');
}
}
void AddOperand(int n)
{
operands_.push_back(n);
}
int Evaluate() const
{
int res = (op_ == '+') ? 0 : 1;
for (int n : operands_) {
if (op_ == '+') {
res += n;
} else {
res *= n;
}
}
return res;
}
private:
char op_;
bool new_operand_;
vector<int> operands_;
};
int Evaluate(string const &s)
{
stack<Exp> st;
st.push(Exp('+'));
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(' &&
i + 1 < s.size())
{
st.push(Exp(s[++i]));
} else if (s[i] == ')') {
Exp e = st.top();
st.pop();
st.top().AddOperand(e.Evaluate());
} else {
st.top().GrowOperands(s[i]);
}
}
return st.top().Evaluate();
}
int main() {
cout << Evaluate("3") << "\n";
cout << Evaluate("(+ 1 2)") << "\n";
cout << Evaluate("(+ 3 4 5)") << "\n";
cout << Evaluate("(+7 (*8 12) (*2 (+9 4) 7) 3)") << "\n";
}
Python version : O(len(string)) complexity
def evaluateExpression(str):
stack, curr_num = [], 0
for char in str:
if char=='(':
if curr_num!=0:
stack.append(curr_num)
curr_num =0
elif char in '*-+':
stack.append(char)
curr_num = 0
elif char in '0123456789':
curr_num = curr_num*10 + int(char)
elif char == ' ':
if curr_num:
stack.append(curr_num)
curr_num = 0
elif char ==')':
if curr_num!=0:
stack.append(curr_num)
curr_num =0
num_list, res = [], 1
while stack and not isinstance(stack[-1],basestring):
num_list.append(stack.pop())
sym = stack.pop()
if sym=='+':
stack.append(sum(num_list))
elif sym=='-':
stack.append(-sum(num_list))
elif sym=='*':
for num in num_list:
res *= num
stack.append(res)
else:
print('Invalid operation!')
else:
print('Error : Invalid symbol !')
if len(stack)!=1:
print('Error ')
return stack[0]
I assume the + in the BNF indicates repeat once or more. Actually to make sense, it
should be (becasue you need at least two operands to make sense):
further I assume integer is:
there are multiple ways to parse it. Since a BNF is given and since it's parsable without lookahead I would approach it like a simple parser, with a super primitive lexer to get some structure into the code:
- Chris November 26, 2017