题目
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers,
+,-,*,/operators and empty spaces. The integer division should truncate toward zero.You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
大意：一个不包含括号，包含空格的计算器
思路
采用堆栈实现。从头到尾扫描字符串：
- 如果是数字，作为当前的各位，之前的数左移一位作为高位。
- 如果是符号，若是加减法，将数字乘以符号压入堆栈。
- 如果是乘除法，从堆栈弹出一个数，与当前数相乘除压回堆栈。
注意，使用后缀表达式，先读出两个数在读出符号，顺序应为：
- 前一个符号的初始值为+（因为读出第一个符号时，对第一个数字的操作一定是压入堆栈，同+的情况）
- 读出一个数字，压入堆栈
- 读出一个符号
- 在读出一个数字
- 根据前一个符号决定当前操作
- 操作完成后将刚读出的符号记为前一个符号。
这样就相当于完成了普通表达式到后缀表达式的转换。
代码
class Solution {
public:
int calculate(string s) {
stack<int> myStack;
char sign = '+';
int num = ,res=;
for (int i = ; i < s.size(); i++){
if (isdigit(s[i]))
num = num * + s[i] - '';
if (((!isdigit(s[i])) && (!isspace(s[i])))||(i==s.size()-)){
if (sign == '+')
myStack.push(num);
if (sign == '-')
myStack.push(num*-);
if (sign == '*'){
num = myStack.top()*num;
myStack.pop();
myStack.push(num);
}
if (sign == '/'){
num = myStack.top() / num;
myStack.pop();
myStack.push(num);
}
sign = s[i];
num = ;
}
}
while (!myStack.empty()){
res += myStack.top();
myStack.pop();
}
return res;
}
};
其他
关于”ctype.h”