CareerCup

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):

expr := int | '(' op expr expr + ')'

further I assume integer is:

integer := ['-'] digit digit +
digit := '0' .. '9'

[] indicates optional

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:

#include <string>
#include <iostream>

using namespace std;

class Parser
{
private:
	size_t offset_;
	string expression_;

public:
	Parser(const string&& expr) : expression_(expr), offset_(0) { }

	int getValue() {
		int result;
		if (!expr(result)) throw "syntax error";
		skipWhiteSpaces();
		if (!isEOF()) throw "syntax error";
		return result;
	}

private:
	// production expr := int | '(' op expr expr + ')'
	bool expr(int& value) {
		int operand;
		int oper; // 0: +, 1: *
		if (matchInteger(value)) { return true; }
		if (!match('(')) return false;
		if (!op(oper)) throw "syntax error, expecting operator";
		if (!expr(value)) throw "syntax error, expecting integer";
		if (!expr(operand)) throw "syntax error, expecting integer";
		do {
			if (oper == 0) value += operand;
			else if (oper == 1) value *= operand;
		} while (expr(operand));
		if (!match(')')) throw "syntax error, expexting ')'";
		return true;
	}

	// production op := '+' | '*'
	bool op(int& op) {
		op = -1;
		if (match('+')) {
			op = 0;
		} else if (match('*')) {
			op = 1;
		} else {
			return false;
		}
		return true;
	}

	// -- from here, primitive lexer functionality --
	bool matchInteger(int& value) {
		int o = offset_;
		bool neg = false;
		bool numbers = false;
		while (o < expression_.size() && expression_[o] == ' ') o++; // read spaces
		if (o < expression_.size() && (neg = (expression_[o] == '-'))) o++; // read '-'
		while (o < expression_.size() && expression_[o] == ' ') o++; // read more spaces		
		value = 0;
		while (o < expression_.size() && expression_[o] >= '0' && expression_[o] <= '9') {
			value = value * 10 + (expression_[o++] - '0');
			numbers = true;
		}
		if (!numbers) return false;	
		if (neg) value = -value;
		offset_ = o;
		return true;
	}

	bool match(char c) {
		skipWhiteSpaces();
		if (isEOF()) return false;
		if (expression_[offset_] == c) {
			offset_++;
			return true;
		}
		return false;
	}

	void skipWhiteSpaces() {
		while (!isEOF() && expression_[offset_] == ' ') { ++offset_; }
	}

	bool isEOF() const { return offset_ >= expression_.size(); }
};

int main()
{
	cout << (Parser("3").getValue() == 3) << endl;
	cout << (Parser("(+ 1 2)").getValue() == 3) << endl;
	cout << (Parser("(+ 3 4 5)").getValue() == 12) << endl;
	cout << (Parser("(+7 (*8 12) (*2 (+9 4) 7) 3)").getValue() == 288) << endl;
}

#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]

the questions you posted are stupid. I feel like you are a troll