題目

https://leetcode.com/problems/basic-calculator-ii/

題解

這道題是 中綴表達式求值 的簡化版（因為沒有左右括號運算），不過輸入的形式有兩個處理起來不是那么舒服的地方：

1、題目中包含空格，造成了一些干擾，需要忽略

2、輸入是一個字符串，導(dǎo)致數(shù)字需要拼接出來，無法直接使用 split 區(qū)分數(shù)字和運算符

經(jīng)典的中綴表達式求值過程如下

本題代碼

import java.util.HashMap; import java.util.Stack;class Solution {HashMap<Character, Integer> priorityMap; // 運算符優(yōu)先級public int calculate(String s) {initPriortyMap();char[] arr = s.toCharArray();Stack<Integer> s1 = new Stack<>(); // 操作數(shù)棧Stack<Character> s2 = new Stack<>(); // 運算符棧int cur = 0;for (int i = 0; i < arr.length; i++) {if (arr[i] >= '0' && arr[i] <= '9') { // 是數(shù)字cur *= 10;cur += arr[i] - '0';} else if (priorityMap.get(arr[i]) != null) { // 是運算符s1.push(cur);cur = 0;if (s2.isEmpty() || isPrior(arr[i], s2.peek())) { // 若當前運算符大于棧頂運算符優(yōu)先級 則入棧s2.push(arr[i]);} else { // 否則 在當前運算符小于等于棧頂運算符情況下 不斷出棧并運算 將運算結(jié)果入操作數(shù)棧while (s2.size() > 0 && !isPrior(arr[i], s2.peek())) {Character op = s2.pop();Integer n1 = s1.pop();Integer n2 = s1.pop();int res = cal(n1, n2, op);s1.push(res);}s2.push(arr[i]);}}if (i == arr.length - 1) s1.push(cur);}while (!s2.isEmpty()) { // 運算符棧中還有剩余 則一直出棧并運算Character op = s2.pop();Integer n1 = s1.pop();Integer n2 = s1.pop();int res = cal(n1, n2, op);s1.push(res);}return s1.pop();}public boolean isPrior(char op1, char op2) {return priorityMap.get(op1) > priorityMap.get(op2);}public void initPriortyMap() {priorityMap = new HashMap<>(); // 運算符優(yōu)先級priorityMap.put('+', 0);priorityMap.put('-', 0);priorityMap.put('*', 1);priorityMap.put('/', 1);}public int cal(int n1, int n2, char op) {switch (op) {case '+':return n2 + n1;case '-':return n2 - n1;case '*':return n2 * n1;case '/':return n2 / n1;default:System.out.println("op err: " + op);return -1;}} }

官方題解

針對沒有左右括號的中綴表達式，官方給的題解確實比我的方法簡化了很多。

但如果要改造成標準的 包含左右括號的 中綴表達式求值的話，我認為還是我寫的上面的版本比較容易改造。

class Solution {public int calculate(String s) {if (s == null || s.isEmpty()) return 0;int len = s.length();Stack<Integer> stack = new Stack<Integer>();int currentNumber = 0;char operation = '+';for (int i = 0; i < len; i++) {char currentChar = s.charAt(i);if (Character.isDigit(currentChar)) {currentNumber = (currentNumber * 10) + (currentChar - '0');}if (!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar) || i == len - 1) {if (operation == '-') {stack.push(-currentNumber);}else if (operation == '+') {stack.push(currentNumber);}else if (operation == '*') {stack.push(stack.pop() * currentNumber);}else if (operation == '/') {stack.push(stack.pop() / currentNumber);}operation = currentChar;currentNumber = 0;}}int result = 0;while (!stack.isEmpty()) {result += stack.pop();}return result;} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 227. Basic Calculator II | 227. 基本计算器 II（中缀表达式求值）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。