牛客原题
描述
请写一个整数计算器,支持加减乘三种运算和括号。
示例1
输入:
“1+2”
返回值:
3
示例2
输入:
“(2*(3-4))*5”
返回值:
-10
示例3
输入:
“3+2* 3 *4-1”
返回值:
26
思路:从左向右遍历字符串
- 1,遇到数字则入栈,注意数字可能是多位
- 2,遇到左括号入栈
- 3,遇到右括号,符号栈依次出栈结合操作数栈进行计算,直到左括号出现,运算结果入栈;
- 4,遇到运算符,判断前一个运算符和当前运算符的优先级,若前一个运算符优先级大于当前运算符优先级,前一个运算符出栈结合操作数栈进行计算,运算结果入栈;当前运算符入栈;
- 5,字符串遍历完毕,如果运算符栈未空,则触发计算。
package leetcode2;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
public class ExpressionCompute {
public static void main(String[] args) {
ExpressionCompute compute = new ExpressionCompute();
System.out.println(compute.solve("100+100"));
}
// 关注三个点:
// 1,入栈-左括号入栈,运算符号入栈,数字入栈
// 2,运算触发:右括号,优先级高的运算符,字符串遍历完成后
public int solve (String s) {
// write code here
Deque<Character> ops = new ArrayDeque<>();
Deque<Integer> nums = new ArrayDeque<>();
s = s.replaceAll(" ","");
char[] chars = s.toCharArray();
Map<Character,Integer> opsPri = new HashMap<>();
opsPri.put('+',1);
opsPri.put('-',1);
opsPri.put('*',2);
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (c == '(') {
// 入栈1
ops.push(chars[i]);
} else if (c == ')') {
// 触发计算1
cal(ops,nums);
} else if (opsPri.containsKey(c)) {
if (ops.size() > 0) {
char opOld = ops.peek();
// 触发计算2,当前运算符优先级低于或等于前一个运算符
if ( opOld != '(' && opsPri.get(opOld) >= opsPri.get(c)) {
int num2 = nums.pop();
int num1 = nums.pop();
opOld = ops.pop();
int newNum = cal(num1, num2, opOld);
nums.push(newNum);
}
}
// 入栈2
ops.push(c);
} else {
// 识别数字
int n = 0;
int j = i;
while(j < chars.length && Character.isDigit(chars[j])) {
c = chars[j];
n = n*10 + (c - '0');
j++;
}
// todo
i = j-1;
// 入栈3
nums.push(n);
}
}
// 触发计算3
return finalCal(ops,nums);
}
private int finalCal(Deque<Character> ops,Deque<Integer> nums) {
while (ops.size() > 0 && nums.size() > 0) {
char c = ops.pop();
int num2 = nums.pop();
int num1 = nums.pop();
nums.push(cal(num1, num2, c));
}
return nums.pop();
}
private void cal(Deque<Character> ops,Deque<Integer> nums) {
char c = ops.pop();
while (c != '(') {
int num2 = nums.pop();
int num1 = nums.pop();
nums.push(cal(num1,num2,c));
c = ops.pop();
}
}
private int cal(int num1, int num2, char ops) {
int res = 0;
switch (ops) {
case '+':
res = num1 + num2;
break;
case '-':
res = num1 - num2;
break;
case '*':
res = num1 * num2;
break;
default:
res = 0;
break;
}
return res;
}
}