Basic Calculator
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
Analysis:
In this question is not difficult but needs to pay more attention on the output order of a stack.As there might be multiple round brackets ( and ) in the string, it is natural to use stack to store the chars in the string. Here it doesn't matter to use either one or two stacks. For two stacks, one stores the operators and the other stores the numbers. From the start of the string, we can keep pushing each char into the stack(s), only when we met the right bracket ")", compute the value of the expression inside "(" and ")", push the value into stack and continue. When all the chars have been pushed into stack. Check the stacks, we have to continue compute the values according to the operators in stack, until no operators are there.
There are two important points:
- Number in the string may not be of length 1, e.g., "123+456".
- The output from stack is reverse to the operation order. e.g. for expression 1-2+3, the output from stack is 3, 2, 1 and + , -, 3+2-1 is NOT equal to 1-2+3.
To handle these issues:
- Keep counting the number and push it into stack once we meet operators. Don't forget to push the number when the string ends.
- Use temporary stacks to revers the order of expression, then compute the value using correct order.
Let's take an example:
" (1+ (4+5+2)-3)+(6+8)"
1. Keep push the numbers and operators into stacks.
2. When meet the ')', compute the value inside "( )", which is 5+2 = 7, push this value back and continue.
3. Continue the above two steps for the whole string. Compute the rest operations according to the operators inside stack.
4. The result is the top value in the number stack after all the operations. In this example, after computing 9 + 14 = 23, 23 is the result.
Note that, there might be multiple spaces in the string, an easy way is to get rid of the spaces at the beginning, since spaces is not useful for either operator or numbers.
Code(C++):
class Solution {
public:
int compute(stack<int> num, stack<char> ops){
//compute value
while (!ops.empty()){
char op = ops.top();
ops.pop();
int a = num.top();
num.pop();
int b = num.top();
num.pop();
if (op == '+'){
num.push(a+b);
}else if (op == '-'){
num.push(a-b);
}
}
return num.top();
}
string rmsp(string s){
string ss = "";
for (int i=0;i<s.size();i++){
if (s[i]!=' '){
ss += s[i];
}
}
return ss;
}
int calculate(string s) {
stack<int> num;
stack<char> ops;
s = rmsp(s); //remove spaces
int i=0;
int n = -1;
while (i<s.size()){
//current position is a (part of) number
if (s[i]>='0' && s[i]<='9'){
if (n==-1){n = 0;}
n = n * 10 + s[i]-'0';
i++;
}else{
if (n != -1){
num.push(n); //push number to stack
n = -1; // set n to zero for new number
}
// ) compute value inside round brackets
if (s[i] == ')'){
stack<int> tmp_num;
stack<char> tmp_ops;
while (ops.top()!='('){
tmp_ops.push(ops.top());
ops.pop();
tmp_num.push(num.top());
num.pop();
}
tmp_num.push(num.top());
num.pop();
num.push(compute(tmp_num, tmp_ops));
ops.pop(); //pop ')' from stack
} else {
ops.push(s[i]);
}
i++;
}
}
if (n!=-1){
num.push(n);
}
stack<int> tmp_num;
stack<char> tmp_ops;
while (!ops.empty()){
tmp_ops.push(ops.top());
ops.pop();
tmp_num.push(num.top());
num.pop();
}
tmp_num.push(num.top());
num.pop();
return compute(tmp_num, tmp_ops);
}
};
Code(Python):
class Solution(object):
def compute(self, num, ops):
while len(ops) != 0:
op = ops.pop()
if op == '+':
num.append(num.pop() + num.pop())
else:
num.append(num.pop() - num.pop())
return num[-1]
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
#remove spaces
s = s.replace(' ', '')
num = []
ops = []
i = 0
n = ''
while i < len(s):
if s[i] >= '0' and s[i] <='9':
n = n + s[i]
i += 1
else:
if n != '':
num.append(int(n))
n = ''
if s[i] == ')':
tmp_num = []
tmp_ops = []
while ops[-1]!= '(':
tmp_ops.append(ops.pop())
tmp_num.append(num.pop())
tmp_num.append(num.pop())
ops.pop()
num.append( self.compute(tmp_num, tmp_ops) )
else:
ops.append(s[i])
i += 1
if n!= '':
num.append(int(n))
tmp_num = []
tmp_ops = []
while len(ops) != 0:
tmp_ops.append(ops.pop())
tmp_num.append(num.pop())
tmp_num.append(num.pop())
return self.compute(tmp_num, tmp_ops)
No comments:
Post a Comment