题目描述
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -,非负整数和空格 。
示例 1:
输入: "1 + 1"
输出: 2
示例 2:
输入: " 2-1 + 2 "
输出: 3
示例 3:
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
说明:
你可以假设所给定的表达式都是有效的。
请不要使用内置的库函数 eval。
。
算法1
遍历 使用栈来解决括号改变的计算优先级别
使用双指针解决数字的转化问题
C++ 代码
class Solution {
public:
stack<int> stNum;
stack<char> stOp;
int Calc(char op) {
int ret = 0;
int a = stNum.top(); stNum.pop();
int b = stNum.top(); stNum.pop();
if (op == '+') {
return b + a;
}
else if (op == '-') {
return a - b;
}
return 0;
}
int calculate(string s) {
reverse(s.begin(),s.end());
for (int i = 0; i < s.size(); i++) {
if (s[i] == ')') {
stOp.push(')');
}
else if (s[i] == '+') {
stOp.push('+');
}
else if (s[i] == '-') {
stOp.push('-');
}
else if (s[i] == ' ') {
continue;
}
else if(s[i] == '(') {
//符号出栈 计算结果入栈 一直到对应的'('出栈
while(1){
char op = stOp.top(); stOp.pop();
if (op == ')') break;
int ret = Calc(op);
stNum.push(ret);
}
}
else {
int l = i; int r = l;
//双指针得到当前非数字的左右端点 转换成数字
while (r < s.size() && s[r] >= '0' && s[r] <= '9')
r++;
string strNum = s.substr(l, r - l);
reverse(strNum.begin(), strNum.end());
int n = atoi(strNum.c_str());
stNum.push(n);
i = r - 1;
}
}
while (!stOp.empty()) {
char op = stOp.top(); stOp.pop();
int ret = Calc(op);
stNum.push(ret);
}
return stNum.top();;
}
};