數據結構與算法 c語言，數據結構與算法 | LeetCode 224. Basic Calculator

原文鏈接：https://wangwei.one/posts/alg...

前面，我們學習了 棧的實現及其應用 ，今天我們基于棧，來實現一個簡單的計算器功能。

簡單計算器實現

Leetcode 224. Basic Calculator

實現一個能夠對簡單的表達式進行計算的基礎計算器。

表達式字符串包含括號 ( 、)，加號(+)，減號(-)，非負整數以及空格(' ')。

Example 1:

Input: "1 + 1"
Output: 2

數據結構與算法 c語言？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% 的提交記錄 ? 。

思路

1. 先對表達式進行校驗，去除空格，并轉化為ArrayList，如果按照一個字符一個字符去遍歷的到，要是表達式中存在多位的整數，就行不通了。
2. 對轉化后的 ArrayList 進行遍歷，遇到數字，直接壓入操作數棧。

3. 遇到操作符，則進行需要進行一系列的判斷，特別是遇到括號的處理：

   1. 操作符棧為空的情況下，直接入棧；
   2. 比較 新的操作符 與 操作符棧頂元素 的優先級，優先級高，則直接入棧。如果它們有一個或都是左括號，則直接入棧；
   3. 如果優先級低或相同，則對前面的表達式進行遞歸計算，將最后的結果壓入操作數棧。之后，在遞歸調用自身，壓入新的操作符。
4. 遍歷結束后，在對操作數站進行最后一次遞歸計算；
5. 去除操作數棧的棧頂元素。

代碼如下

數據結構嚴蔚敏。里面用到的 LinkedStack 是我們前面自己實現的鏈表棧，當然使用 ArrayStack 也可以。

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<Integer> operand;private IStack<String> operator;private Set<String> highOperator;private Set<String> lowOperator;private Set<String> parentheses;private Set<String> 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<String> express = convertExpr(s);for (String str : express) {if (!operatorSet.contains(str)) {operand.push(Integer.valueOf(str));} else {pushOperator(str);}}// 對余下的操作數進行計算，得到最后的結果operandCalcu();return operand.pop();}/*** 轉換表達式* <p>* 1. 去除空格* 2. 拆分出有效的數字** @param expr* @return*/private ArrayList<String> convertExpr(String expr) {ArrayList<String> result = new ArrayList<>();// remove empty spacesString 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.

思路

1. 處理多位整數。比如解析123，第一次循環為 1 10 + 2 = 12，第二次循環為 12 10 + 3 = 123；
2. 處理加減號。不是存儲入到操作符棧，而是轉為正負號，待到下一次循環時，與前面的累計結果進行相加；
3. 處理括號。如果遇到 左括號 (，就將前面累計的結果與正負存儲操作數棧，并將累計結果清空，正負號標記為正。等到遇到右括號 )時，就將這一次累計的結果與操作數棧頂存儲的累計結果進行累加，得到一個最終結果；

代碼

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<Integer> 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))"));}}

源碼

知道原理是一回事，自己動手去實現，又是另外一回事！

參考資料

• 《數據結構與算法之美》
• https://time.geekbang.org/col...
• https://www.youtube.com/watch...