基本计算器 II
问题描述
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。整数除法仅保留整数部分。你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。详见leetcode227
问题分析
我们可以通过栈来解决计算器的相关问题。我们可以设置一个pre变量来记录每一个数字之前的符号，当我们遇到一个数字时，查看pre变量的值，如果是+，则将该数字入栈，如果是-，则将该数字的相反数入栈，如果是*，则出栈一个元素，用出栈元素乘以当前数字，将结果压栈，如果是/，出栈一个元素，用出栈元素除以当前数字，将结果压栈，注意去除字符串中可能出现的空格，对于字符串中连续的数组成的一个数字，可以通过乘以10加当前遍历数的方式，初始时，我们可以假设pre变量为+。
代码实现
public int calculate(String s) {
Stack<Integer> stack = new Stack<>();
int num = 0;
char pre = '+';
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + c - '0';
}
if (!Character.isDigit(c) && s.charAt(i) != ' ' || i == s.length() - 1) {
if (pre == '+' || pre == '-') {
stack.push(pre == '+' ? num : (-1) * num);
} else {
int x = stack.pop();
if (pre == '*') {
x *= num;
} else {
x /= num;
}
stack.push(x);
}
pre = c;
num = 0;
}
}
int res = 0;
while (!stack.isEmpty()) {
res += stack.pop();
}
return res;
}
逆波兰表达式求值
问题描述
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意：有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。每个操作数（运算对象）都可以是一个整数或者另一个表达式。两个整数之间的除法总是 向零截断 。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用 32 位 整数表示。详见leetcode150
问题分析
遍历字符数组，当我们遇到数字时，就将其入栈，遇到运算符时，出栈两个元素，进行运算符对应的运算，并将运算结果入栈，返回最终的栈中元素，即为运算结果。
代码实现
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for(int i=0;i<tokens.length;i++){
if(!Character.isDigit(tokens[i].charAt(0))&&tokens[i].length()==1){
char c = tokens[i].charAt(0);
int x = stack.pop();
int y = stack.pop();
int res=0;
if(c=='+'){
res = y+x;
}else if(c=='-'){
res = y-x;
}else if(c=='*'){
res = y*x;
}else if(c=='/'){
res = y/x;
}
stack.push(res);
}else{
stack.push(Integer.parseInt(tokens[i]));
}
}
return stack.pop();
}
