space_scene
原文鏈接：https://wangwei.one/posts/algoDS-java-leetcode-224-basic-calculator.html
前面，我們學(xué)習(xí)了 棧的實(shí)現(xiàn)及其應(yīng)用 ，今天我們基于棧，來實(shí)現(xiàn)一個(gè)簡單的計(jì)算器功能。
簡單計(jì)算器實(shí)現(xiàn)
Leetcode 224. Basic Calculator
實(shí)現(xiàn)一個(gè)能夠?qū)唵蔚谋磉_(dá)式進(jìn)行計(jì)算的基礎(chǔ)計(jì)算器。
表達(dá)式字符串包含括號(hào) ( 、)，加號(hào)(+)，減號(hào)(-)，非負(fù)整數(shù)以及空格(' ')。
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
使用兩個(gè)棧來實(shí)現(xiàn)
根據(jù) 棧的實(shí)現(xiàn)及其應(yīng)用 中學(xué)到的表達(dá)式求值的解法：
編譯器會(huì)使用兩個(gè)棧來實(shí)現(xiàn)，一個(gè)棧用來保存操作數(shù)，另一個(gè)棧用來保存運(yùn)算符。從左向右遍歷表達(dá)式，遇到數(shù)字直接壓入操作數(shù)棧，遇到操作符，就與運(yùn)算符棧頂元素進(jìn)行比較。
如果比運(yùn)算符棧頂元素的優(yōu)先級(jí)高，就將當(dāng)前運(yùn)算符壓入棧；如果比運(yùn)算符棧頂元素的優(yōu)先級(jí)低或者相同，從運(yùn)算符棧中取棧頂運(yùn)算符，從操作數(shù)棧的棧頂取 2 個(gè)操作數(shù)，然后進(jìn)行計(jì)算，再把計(jì)算完的結(jié)果壓入操作數(shù)棧，繼續(xù)比較。
下面是我根據(jù)上面思路，寫出來的第一版實(shí)現(xiàn)，相比于網(wǎng)上巧妙的解題方法，確實(shí)復(fù)雜很多，在LeetCode的運(yùn)行時(shí)間為 195 ms ，只超過了 8.14% 的提交記錄 ?? 。
思路
- 先對(duì)表達(dá)式進(jìn)行校驗(yàn)，去除空格，并轉(zhuǎn)化為ArrayList，如果按照一個(gè)字符一個(gè)字符去遍歷的到，要是表達(dá)式中存在多位的整數(shù)，就行不通了。
- 對(duì)轉(zhuǎn)化后的 ArrayList 進(jìn)行遍歷，遇到數(shù)字，直接壓入操作數(shù)棧。
- 遇到操作符，則進(jìn)行需要進(jìn)行一系列的判斷，特別是遇到括號(hào)的處理：
- 操作符棧為空的情況下，直接入棧；
- 比較 新的操作符 與 操作符棧頂元素 的優(yōu)先級(jí)，優(yōu)先級(jí)高，則直接入棧。如果它們有一個(gè)或都是左括號(hào)，則直接入棧；
- 如果優(yōu)先級(jí)低或相同，則對(duì)前面的表達(dá)式進(jìn)行遞歸計(jì)算，將最后的結(jié)果壓入操作數(shù)棧。之后，在遞歸調(diào)用自身，壓入新的操作符。
- 遍歷結(jié)束后，在對(duì)操作數(shù)站進(jìn)行最后一次遞歸計(jì)算；
- 去除操作數(shù)棧的棧頂元素。
代碼如下
里面用到的 LinkedStack 是我們前面自己實(shí)現(xiàn)的鏈表?xiàng)?，?dāng)然使用 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;
/**
* 簡單計(jì)算器實(shí)現(xiàn)
*
* @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);
}
/**
* 運(yùn)算表達(dá)式
*
* @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);
}
}
// 對(duì)余下的操作數(shù)進(jìn)行計(jì)算，得到最后的結(jié)果
operandCalcu();
return operand.pop();
}
/**
* 轉(zhuǎn)換表達(dá)式
* <p>
* 1. 去除空格
* 2. 拆分出有效的數(shù)字
*
* @param expr
* @return
*/
private ArrayList<String> convertExpr(String expr) {
ArrayList<String> 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;
}
/**
* 運(yùn)算符入棧
*
* @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;
}
// 第一次以后入棧，先比較優(yōu)先級(jí)，高優(yōu)先級(jí)，則入棧
if (priority(operatorSign, prevOperator)) {
operator.push(operatorSign);
} else {
// 否則先對(duì)前面的表達(dá)式進(jìn)行計(jì)算
operandCalcu();
pushOperator(operatorSign);
}
}
}
/**
* 從操作數(shù)棧取出兩個(gè)操作數(shù)進(jìn)行計(jì)算
*/
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();
}
/**
* 比較優(yōu)先級(jí)
*
* @param next
* @param prev
* @return
*/
private boolean priority(String next, String prev) {
return (highOperator.contains(next)
&& lowOperator.contains(prev))
|| "(".equals(prev)
|| "(".equals(next);
}
/**
* 對(duì)兩個(gè)數(shù)字進(jìn)行計(jì)算
*
* @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);
}
}
巧妙的解法
下面我們來看看網(wǎng)上比較好的解法，相比于我的代碼，簡直不要爽太多，膜拜…… LeetCode上運(yùn)行只需要耗時(shí) 27 ms.
思路
- 處理多位整數(shù)。比如解析123，第一次循環(huán)為 1 * 10 + 2 = 12，第二次循環(huán)為 12 * 10 + 3 = 123；
- 處理加減號(hào)。不是存儲(chǔ)入到操作符棧，而是轉(zhuǎn)為正負(fù)號(hào)，待到下一次循環(huán)時(shí)，與前面的累計(jì)結(jié)果進(jìn)行相加；
- 處理括號(hào)。如果遇到
左括號(hào) (，就將前面累計(jì)的結(jié)果與正負(fù)存儲(chǔ)操作數(shù)棧，并將累計(jì)結(jié)果清空，正負(fù)號(hào)標(biāo)記為正。等到遇到右括號(hào) )時(shí)，就將這一次累計(jì)的結(jié)果與操作數(shù)棧頂存儲(chǔ)的累計(jì)結(jié)果進(jìn)行累加，得到一個(gè)最終結(jié)果；
代碼
package one.wangwei.leetcode.stack;
import java.util.Stack;
/**
* 簡單計(jì)算器實(shí)現(xiàn)
*
* @author https://wangwei.one
* @date 2019/1/18
*/
public class BasicCalculator {
/**
* 運(yùn)算表達(dá)式
*
* @param s
* @return
*/
public int calculate(String s) {
// 操作數(shù)棧
Stack<Integer> stack = new Stack<>();
// 正負(fù)號(hào)
int sign = 1;
// 累計(jì)結(jié)果
int result = 0;
for (int i = 0; i < s.length(); i++) {
if (Character.isDigit(s.charAt(i))) {
// 字符轉(zhuǎn)換
int num = s.charAt(i) - '0';
// 處理多位整數(shù)
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))"));
}
}
知道原理是一回事，自己動(dòng)手去實(shí)現(xiàn)，又是另外一回事！
