LeetCode Q224: Basic Calculator (hard)

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23

Solution:
Using stack. Following is my solution which although right but didn't pass all the test due to LTE. However, the theoretical bound of time complexity is till O(n) though.

	class Solution {
	public:
	long nextNum(string s, int& i){
	long num;
	int base=0;
	while(i<s.length()&&s[i]>='0'&&s[i]<='9')
	num = num*pow(10, base++)+(s[i++]-'0');
	return num;
	}
	void compute(stack<long>& numStack, stack<char>& charStack){
	long num1=numStack.top();
	numStack.pop();
	long num2=numStack.top();
	numStack.pop();
	if(charStack.top()=='+')
	numStack.push(num1+num2);
	if(charStack.top()=='-')
	numStack.push(num2-num1);
	charStack.pop();
	}
	int calculate(string s) {
	stack<long> numStack;
	stack<char> charStack;
	int i=0;
	while(i<s.length()){
	char c = s[i];
	if(c=='+'||c=='-'){
	charStack.push(c);
	i++;
	continue;
	}
	if(c=='('){
	charStack.push(c);
	i++;
	continue;
	}
	if(c==')'){
	charStack.pop();
	if(!charStack.empty()&&(charStack.top()=='+'||charStack.top()=='-'))
	compute(numStack, charStack);
	i++;
	continue;
	}
	if(c>='0'&&c<='9'){
	long num = nextNum(s, i);
	numStack.push(num);
	if(!charStack.empty()&&(charStack.top()=='+'||charStack.top()=='-'))
	compute(numStack, charStack);
	continue;
	}
	if(c==' '){
	i++;
	continue;
	}
	}
	return numStack.top();
	}
	};

view raw Q224BasicCalculator.cpp hosted with ❤ by GitHub

Solutoin 2: Basically, the idea is very similar to my solution, but using less stack operation which I think is the reason that makes my problem slow.

	int calculate(string s) {
	stack<int> nums, ops;
	int rst=0;
	int num=0;
	int sign=1;
	for(char c: s){
	if(isdigit(c)){
	num = num*10+c-'0';
	}else{
	rst += sign*num;
	num=0;
	if(c=='+') sign=1;
	if(c=='-') sign=-1;
	if(c=='('){
	ops.push(sign);
	nums.push(rst);
	rst=0;
	sign=1;
	}
	if(c==')'&&ops.size()){
	rst = ops.top() * rst + nums.top();
	ops.pop(); nums.pop();
	}
	}
	}
	return rst + sign * num;
	}

view raw Q224-2.cpp hosted with ❤ by GitHub