原文链接：
前面，我们学习了有关的 ，今天我们基于栈，来实现一个简单的计算器功能。
简单计算器实现
Leetcode 224.
实现一个能够对简单的表达式进行计算的基础计算器。
表达式字符串包含括号 ( 、)，加号(+)，减号(-)，非负整数以及空格(' ')。
Example 1:
Input: "1 + 1"Output: 2复制代码
Example 2:
Input: " 2-1 + 2 "Output: 3复制代码
Example 3:
Input: "(1+(4+5+2)-3)+(6+8)"Output: 23复制代码
使用两个栈来实现
根据 中学到的表达式求值的解法：
编译器会使用两个栈来实现，一个栈用来保存操作数，另一个栈用来保存运算符。从左向右遍历表达式，遇到数字直接压入操作数栈，遇到操作符，就与运算符栈顶元素进行比较。
如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
下面是我根据上面思路，写出来的第一版实现，相比于网上巧妙的解题方法，确实复杂很多，在LeetCode的运行时间为 195 ms ，只超过了 8.14% 的提交记录 ? 。
思路
- 先对表达式进行校验，去除空格，并转化为ArrayList，如果按照一个字符一个字符去遍历的到，要是表达式中存在多位的整数，就行不通了。
- 对转化后的 ArrayList 进行遍历，遇到数字，直接压入操作数栈。
- 遇到操作符，则进行需要进行一系列的判断，特别是遇到括号的处理：
- 操作符栈为空的情况下，直接入栈；
- 比较 新的操作符 与 操作符栈顶元素 的优先级，优先级高，则直接入栈。如果它们有一个或都是左括号，则直接入栈；
- 如果优先级低或相同，则对前面的表达式进行递归计算，将最后的结果压入操作数栈。之后，在递归调用自身，压入新的操作符。
- 遍历结束后，在对操作数站进行最后一次递归计算；
- 去除操作数栈的栈顶元素。
代码如下
里面用到的 是我们前面自己实现的链表栈，当然使用 也可以。
package one.wangwei.leetcode.stack;import one.wangwei.algorithms.datastructures.stack.IStack;import one.wangwei.algorithms.datastructures.stack.impl.LinkedStack;import java.util.ArrayList;import java.util.HashSet;import java.util.Set;/** * 简单计算器实现 * * @author https://wangwei.one * @date 2019/1/18 */public class MyBasicCalculator { private IStack operand; private IStack operator; private Set highOperator; private Set lowOperator; private Set parentheses; private Set operatorSet; public MyBasicCalculator() { this.operand = new LinkedStack<>(); this.operator = new LinkedStack<>(); this.parentheses = new HashSet<>(); this.parentheses.add("("); this.parentheses.add(")"); this.highOperator = new HashSet<>(); this.highOperator.add("*"); this.highOperator.add("/"); this.lowOperator = new HashSet<>(); this.lowOperator.add("+"); this.lowOperator.add("-"); this.operatorSet = new HashSet<>(); this.operatorSet.addAll(highOperator); this.operatorSet.addAll(lowOperator); this.operatorSet.addAll(parentheses); } /** * 运算表达式 * * @param s * @return */ public int calculate(String s) { if (s == null || s.isEmpty()) { throw new RuntimeException("Expression Invalid! expr=" + s); } ArrayList express = convertExpr(s); for (String str : express) { if (!operatorSet.contains(str)) { operand.push(Integer.valueOf(str)); } else { pushOperator(str); } } // 对余下的操作数进行计算，得到最后的结果 operandCalcu(); return operand.pop(); } /** * 转换表达式 * * 1. 去除空格 * 2. 拆分出有效的数字 * * @param expr * @return */ private ArrayList
convertExpr(String expr) { ArrayList result = new ArrayList<>(); // remove empty spaces String trimExpr = expr.replaceAll("\\s+", ""); String tmpIntStr = ""; for (Character ch : trimExpr.toCharArray()) { String str = ch.toString(); if (operatorSet.contains(str)) { if (!tmpIntStr.isEmpty()) { result.add(tmpIntStr); tmpIntStr = ""; } result.add(str); } else { tmpIntStr = tmpIntStr + str; } } if (!tmpIntStr.isEmpty()) { result.add(tmpIntStr); } return result; } /** * 运算符入栈 * * @param operatorSign */ private void pushOperator(String operatorSign) { String prevOperator = null; if (!operator.empty()) { prevOperator = operator.peek(); } // 第一次入栈 if (prevOperator == null) { operator.push(operatorSign); } else { if (")".equals(operatorSign) && "(".equals(prevOperator)) { operator.pop(); return; } // 第一次以后入栈，先比较优先级，高优先级，则入栈 if (priority(operatorSign, prevOperator)) { operator.push(operatorSign); } else { // 否则先对前面的表达式进行计算 operandCalcu(); pushOperator(operatorSign); } } } /** * 从操作数栈取出两个操作数进行计算 */ private void operandCalcu() { if (operator.empty()) { return; } String sign = operator.peek(); if ("(".equals(sign)) { return; } sign = operator.pop(); int after = operand.pop(); int front = operand.pop(); int value = calcIntegers(front, after, sign); operand.push(value); operandCalcu(); } /** * 比较优先级 * * @param next * @param prev * @return */ private boolean priority(String next, String prev) { return (highOperator.contains(next) && lowOperator.contains(prev)) || "(".equals(prev) || "(".equals(next); } /** * 对两个数字进行计算 * * @param front * @param after * @param sign * @return */ private int calcIntegers(int front, int after, String sign) { switch (sign) { case "+": return front + after; case "-": return front - after; case "*": return front * after; case "/": return front / after; default: throw new RuntimeException("Sign Invalid! sign=" + sign); } } public static void main(String[] args) { long startTime = System.currentTimeMillis(); MyBasicCalculator solution = new MyBasicCalculator(); System.out.println(solution.calculate("1 + 1 - 3 + 4 - (8 + 2) - 4 + 3 - 1 - 4 + 6 - 9 + 1")); System.out.println(solution.calculate("(1+(4+5+2)-3)+(6+8)")); System.out.println(solution.calculate("1-(5)")); System.out.println(solution.calculate("2-4-(8+2-6+(8+4-(1)+8-10))")); System.out.println(System.currentTimeMillis() - startTime); }}复制代码 巧妙的解法
下面我们来看看网上比较好的解法，相比于我的代码，简直不要爽太多，膜拜…… LeetCode上运行只需要耗时 27 ms.
思路
- 处理多位整数。比如解析123，第一次循环为 1 * 10 + 2 = 12，第二次循环为 12 * 10 + 3 = 123；
- 处理加减号。不是存储入到操作符栈，而是转为正负号，待到下一次循环时，与前面的累计结果进行相加；
- 处理括号。如果遇到
左括号 (，就将前面累计的结果与正负存储操作数栈，并将累计结果清空，正负号标记为正。等到遇到右括号 )时，就将这一次累计的结果与操作数栈顶存储的累计结果进行累加，得到一个最终结果；
代码
package one.wangwei.leetcode.stack;import java.util.Stack;/** * 简单计算器实现 * * @author https://wangwei.one * @date 2019/1/18 */public class BasicCalculator { /** * 运算表达式 * * @param s * @return */ public int calculate(String s) { // 操作数栈 Stack stack = new Stack<>(); // 正负号 int sign = 1; // 累计结果 int result = 0; for (int i = 0; i < s.length(); i++) { if (Character.isDigit(s.charAt(i))) { // 字符转换 int num = s.charAt(i) - '0'; // 处理多位整数 while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) { num = num * 10 + s.charAt(i + 1) - '0'; i++; } result += num * sign; } else if (s.charAt(i) == '+') { sign = 1; } else if (s.charAt(i) == '-') { sign = -1; } else if (s.charAt(i) == '(') { stack.push(result); stack.push(sign); result = 0; sign = 1; } else if (s.charAt(i) == ')') { result = result * stack.pop() + stack.pop(); } } return result; } public static void main(String[] args) { BasicCalculator calculator = new BasicCalculator(); System.out.println(calculator.calculate("2-4-(8+2-6 + (8 +4 -(1)+8-10))")); }}复制代码 参考资料
- 《》