这是一道 中等难度 的题。
题目来自：https://leetcode.cn/problems/basic-calculator-ii/
题目
提示：
-
-
s 由整数和算符 (‘+‘, ‘–‘, ‘*‘, ‘/‘) 组成，中间由一些空格隔开
-
s 表示一个 有效表达式
-
表达式中的所有整数都是非负整数，且在范围 内
-
题目数据保证答案是一个 32-bit 整数
示例 1：
输入：s = "3+2*2"
输出：7
示例 2：
输入：s = " 3/2 "
输出：1
示例 3：
输入：s = " 3+5 / 2 "
输出：5
题解
01
解题思路
本题给定的输入算式是一个 中缀表达式 ，也是我们日常生活中使用最多的，对人类阅读非常友好。 但对计算机而言，中缀表达式其实并不是很好处理，因为算符优先级的关系，先出现的不一定先算，如：2 + 3 * 2，应该先算乘法再算加法。 由上一篇【算法题解】16. 逆波兰表达式(后缀表达式)求值 可知，后缀表达式 不存在算符优先级的问题，所以本题解题思路为将“中缀表达式” 转换为“后缀表达式”，然后再对后缀表达式求值。 那么如何将“中缀表达式” 转换为“后缀表达式” 呢？
因为中缀表达式中后出现的操作符可能会先执行，符合后进先出的特性，所以我们还是可以使用栈的特性来实现。 循环遍历中缀表达式： 1. 当前操作符的优先级 大于 栈顶操作符时：直接入栈，因为出栈时优先级高的排在了前面，也就会优先计算。 2. 当前操作符的优先级 小于等于 栈顶操作符时：即先出现的先算，所以需要将前面优先级大于等于当前操作符的所有操作符依次出栈，这个出栈的顺序就是执行顺序。 以：2 + 3 * 2 + 1为例：
后缀表达式求值，同样使用的是栈的特性。
遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。 以 [“2″,”1″,”+”,”3″,”*”]为例：
由以上两个步骤会发现，中缀表达式转后缀表达式的时候，后缀表达式刚好是一个一个字符按顺序生成的。 这与后缀表达式求值的遍历顺序一模一样，所以我们可以将上述两个步骤进行合并，生成后缀表达式的同时顺便就可以将其求值了。 最终解题思路
所以最终的计算逻辑为，利用两个栈，一个操作符栈（用于中缀转后缀），一个数字栈（用于后缀表达式求值）直接对中缀表达式求值。 循环遍历中缀表达式中的每一个字符：
遇到数字则压入数字栈。 遇到操作符时：
如果操作符栈为空，则压入操作符栈。 如果操作符栈不空： i. 如果新的操作符比栈顶的操作符优先级高，则入栈，如 “*” 的优先级高于 “+”。 ii. 否则，取出 操作符栈 中的操作符与 数字栈 顶的两个元素计算，并将结果重新压入数字栈。重复这个操作，直到操作符栈为空或者栈顶操作符的优先级小于当前操作符；最后将当前操作符入栈。
当循环结束后，需要将操作符栈中的操作符逐个取出，然后和数字栈中的数字进行计算。
02
Java 代码实现
class Solution {
private Deque<Integer> numStack = new LinkedList<Integer>();
private Deque<Character> optStack = new LinkedList<Character>();
public int calculate(String s) {
int n = s.length();
for(int i = 0; i < n; i++){
char c = s.charAt(i);
if(this.isNumber(c)){
int num = 0;
while(i < n && this.isNumber(s.charAt(i))){
num = num * 10 + (s.charAt(i) - '0');
i++;
}
numStack.push(num);
i = i - 1;
}else{
if(c == ' '){
continue;
}
// 操作符
while(!optStack.isEmpty() && this.getRank(optStack.peek()) >= this.getRank(c)){
this.calc(numStack, optStack);
}
optStack.push(c);
}
}
// 清空操作符栈，让每一个操作符都参与运算
while(!optStack.isEmpty()){
this.calc(numStack, optStack);
}
return numStack.pop();
}
private boolean isNumber(char c){
return c >= '0' && c <= '9';
}
private int getRank(char opt){
if(opt == '+' || opt == '-'){
return 1;
}else{
return 2;
}
}
private void calc(Deque<Integer> numStack, Deque<Character> optStack){
char opt = optStack.pop();
int num2 = numStack.pop();
int num1 = numStack.pop();
switch (opt){
case '+':
numStack.push(num1 + num2);
break;
case '-':
numStack.push(num1 - num2);
break;
case '*':
numStack.push(num1 * num2);
break;
default:
numStack.push(num1 / num2);
}
}
}
03
Go 代码实现
func calculate(s string) int {
numStack, optStack := []int{}, []byte{}
n := len(s)
for i := 0; i < n; i++ {
if isNumber(s[i]) {
num := 0
for i < n && isNumber(s[i]) {
num = num * 10 + int(s[i] - '0')
i++
}
numStack = append(numStack, num)
i = i - 1
} else {
if s[i] == ' '{
continue
}
// 操作符
for len(optStack) != 0 && getRank(s[i]) <= getRank(optStack[len(optStack) - 1]) {
numStack, optStack = calc(numStack, optStack);
}
optStack = append(optStack, s[i])
}
}
// 清空操作符栈，让每一个操作符都参与运算
for len(optStack) != 0 {
numStack, optStack = calc(numStack, optStack)
}
return numStack[0]
}
func isNumber(ch byte) bool {
return ch >= '0' && ch <= '9'
}
func getRank(opt byte) int {
if opt == '+' || opt == '-' {
return 1
}else{
return 2
}
}
func calc(numStack []int, optStack []byte) ([]int, []byte) {
opt := optStack[len(optStack) - 1]
optStack = optStack[:len(optStack) - 1]
num1, num2 := numStack[len(numStack) - 2], numStack[len(numStack) - 1]
numStack = numStack[:len(numStack) - 2]
switch opt {
case '+':
numStack = append(numStack, num1 + num2)
case '-':
numStack = append(numStack, num1 - num2)
case '*':
numStack = append(numStack, num1 * num2)
default:
numStack = append(numStack, num1 / num2)
}
return numStack, optStack
}
04
复杂度分析
时间复杂度：, N 为字符串长度，循环N次，其中每个字符的处理时间复杂度都是常数。
空间复杂度：, N 为字符串长度，两个栈最多会存放 N 个元素。
END
点个
在看你最好看 原文始发于微信公众号（i余数）：【算法题解】17. 实现一个包含“加减乘除”的基本计算器
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/193968.html
