1、题目描述
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 .
Example 1:
Input: "1 + 1"
Output: 2
Example 2:
Input: " 2-1 + 2 "
Output: 3
Example 3:
Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23
Note:
You may assume that the given expression is always valid.
Do not use the eval built-in library function.
2、问题描述：
- 设计一个计算器，具有加减和（）功能。
3、问题关键：
- 两个堆栈，一个存放数据，一个存放运算符。
- 注意去掉空格。
4、C++代码：
/*
栈：符号栈和数栈。
op-stack
num-stack 1
如果遇到（和+直接放在op中，数字放在num中，
*/
class Solution {
public:
void calc(stack<char> &op, stack<int> &num) {
int y = num.top();
num.pop();
int x = num.top();
num.pop();
if (op.top() == '+' ) num.push(x + y);
else num.push(x - y);
op.pop();
}
int calculate(string s) {
stack<char> op;
stack<int> num;
for (int i = 0; i < s.size(); i ++) {
char c = s[i];
if (c == ' ') continue;
if (c == '(' || c == '+' || c == '-') op.push(c);
else if (c == ')') {
op.pop();
if (op.size() && op.top() != '(')
calc(op, num);
}
else {
int j = i;
while(j < s.size() && isdigit(s[j])) j ++;
num.push(atoi(s.substr(i, j - i).c_str()));
i = j - 1;
if (op.size() && op.top() != '(')
calc(op, num);
}
}
return num.top();
}
};
