当前位置：首页 > news >正文

【表达式求值算法】拆解复杂问题：实现计算器

news 来源：原创 2024/9/25 5:09:16

表达式求值算法是个 Hard 级别的问题，本次就来解决它。最终实现一个包含如下功能的计算器：

1.输入一个字符串，可以包含 + - * / 、数字、括号以及空格，算法返回运行结果。

2.要符合运算规则，括号的优先级最高，先乘除后加减。

3.除号是整数除法，无论正负都向0取整（5/2=2，-5/2=-2）。

4.可以假定输入的算式一定合法，且计算过程不会出现整型溢出，不会出现除数为0的意外情况。

比如输入如下字符串，算法会返回9：

“3 * (2-6 / (3 - 7))”

其关键在于层层拆解问题，化整为零，逐个击破，相信这种思维方式能帮助大家解决各种复杂问题。

下面就来拆解，先从最简单的一个问题开始。

处理加减法

如果输入的算式只包含加减法，而且不存在空格，以字符串算式“1-12+3”为例，来说一个很简单的思路：

1.先给第一个数字加一个默认符号“+”，变成“+1-12+3”。

2.把一个运算符和数字组成一对，也就是三对 +1，-12，+3，把它们转化成数字，然后放到一个栈中。

3.将栈中所有的数字求和，就是原算式的结果。

直接看代码：

import java.util.Stack;public class Calculate {public int calculate(String s) {Stack<Integer> stack = new Stack();// 记录 num 前的符号，初始化为+char sign = '+';// 记录算式中的数字int num = 0;for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);// 如果是数字，连续读取出来if (c >= '0' && c <= '9') {num = 10 * num + (c - '0');}// 如果不是数字，就是遇到了下一个符号，之前的数字和符号就要入栈if ((c < '0' || c > '9') || i == s.length() - 1) {switch (sign) {case '+':stack.push(num);break;case '-':stack.push(-num);break;}// 更新符号为当前符号，数字清零sign = c;num = 0;}}// 将栈中所有结果求和就是答案int res = 0;while (!stack.empty()) {res += stack.pop();}return res;}public static void main(String[] args) {Calculate calculate = new Calculate();int res = calculate.calculate("1-12+3");System.out.println(res);}
}

处理乘除法

思路和仅处理加减法没什么区别，拿字符串“2-3*4+5”举例，核心思路依然是把字符串分解成符号和数字的组合。

比如上述例子就可以分解为 +2，-3，*4，+5几对，其他部分都不用变，在 switch 部分加上对应的 case 就行了。乘除法优先于加减法体现在：乘除法可以和栈顶的数结合然后把结果加入栈；而加减法只能把自己放入栈。空格不是运算符，加个条件直接忽略就行：

import java.util.Stack;public class Calculate {public int calculate(String s) {Stack<Integer> stack = new Stack();// 记录 num 前的符号，初始化为+char sign = '+';// 记录算式中的数字int num = 0;// 记录栈顶元素int pre = 0;for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);// 如果是数字，连续读取出来if (c >= '0' && c <= '9') {num = 10 * num + (c - '0');}// 如果不是数字，就是遇到了下一个符号，之前的数字和符号就要入栈if ((c < '0' || c > '9') && c != ' ' || i == s.length() - 1) {switch (sign) {case '+':stack.push(num);break;case '-':stack.push(-num);break;case '*':pre = stack.pop();stack.push(pre * num);break;case '/':pre = stack.pop();stack.push(pre / num);break;}// 更新符号为当前符号，数字清零sign = c;num = 0;}}// 将栈中所有结果求和就是答案int res = 0;while (!stack.empty()) {res += stack.pop();}return res;}public static void main(String[] args) {Calculate calculate = new Calculate();int res = calculate.calculate("2-3*4-5");System.out.println(res);}
}

处理括号

这里就到难点了，但其实一点都不难，因为括号具有递归性质，无论括号嵌套多少层，都可以用一个递归搞定。括号包含的算式，直接视为一个数字就行了。（leetcode例题：224.基本计算器）

话不多说，直接上代码：

import java.util.Stack;public class Calculate {public int calculate(String s) {Stack<Character> stack = new Stack();for (int i = s.length() - 1; i >= 0; i--) {stack.push(s.charAt(i));}return helper(stack);}public int helper(Stack<Character> stack) {Stack<Integer> nums = new Stack<>();// 记录 num 前的符号，初始化为+char sign = '+';// 记录算式中的数字int num = 0;// 记录栈顶元素int pre = 0;while (!stack.empty()) {char c = stack.pop();if (c >= '0' && c <= '9') {num = 10 * num + (c - '0');}// 遇到左括号开始递归计算if (c == '(') {num = helper(stack);}// 如果不是数字，就是遇到了下一个符号，之前的数字和符号就要入栈if ((c < '0' || c > '9') && c != ' ' || stack.empty()) {switch (sign) {case '+':nums.push(num);break;case '-':nums.push(-num);break;case '*':pre = stack.pop();nums.push(pre * num);break;case '/':pre = stack.pop();nums.push(pre / num);break;}// 更新符号为当前符号，数字清零sign = c;num = 0;}if (c == ')') {break;}}// 将栈中所有结果求和就是答案int res = 0;while (!nums.empty()) {res += nums.pop();}return res;}
}