此文源自于Leetcode的基本计算机II。

使用Rust语言完成，共计有两个版本。

一个是基础版本（可以完成题目的要求），另一个是在此基础之上的改进（可以完成所有的运算符的要求）。

无论是基础版还是改进版，均使用Rust版本。无其他语言版本。

题目描述

原始题源：点我 中文题源：点我

题目描述：

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。 整数除法仅保留整数部分。

• 示例 1：

输入：s = "3+2*2"
输出：7

• 示例 2：

输入：s = " 3/2 "
输出：1

• 示例 3：

输入：s = " 3+5 / 2 "
输出：5

题目解法

解法1：基础计算解法

思路

• 加法压入栈中
• 减法压入负数的数字
• 乘法和除法直接运算即可，并把结果压入栈中

算法来源：https://leetcode-cn.com/problems/basic-calculator-ii/solution/ji-ben-ji-suan-qi-ii-by-leetcode-solutio-cm28/

代码

rust代码(v1.rs)如下：

/// Solution: https://leetcode-cn.com/problems/basic-calculator-ii/solution/ji-ben-ji-suan-qi-ii-by-leetcode-solutio-cm28/
/// PS：v1只能应对`+-*/`，不能处理带括号情况，甚至是其他优先级的情况
pub fn calculate(s: String) -> i32 {
    let n = s.len();
    let mut stack = vec![];
    let mut pre_sign = '+';
    let mut num = 0;

    for (idx, c) in s.chars().enumerate() {
        if c.is_numeric() {
            num = num * 10 + parse_as_int(c)
        }

        if !c.is_numeric() && !c.is_whitespace() || idx == n - 1 {
            match pre_sign {
                '+' => stack.push(num),
                '-' => stack.push(-num),
                '*' => {
                    let prev = stack.pop().unwrap();
                    stack.push(prev * num);
                }
                '/' => {
                    let prev = stack.pop().unwrap();
                    stack.push(prev / num);
                }
                _ => unreachable!(),
            }
            num = 0;
            pre_sign = c;
        }
    }

    stack.iter().sum()
}

fn parse_as_int(c: char) -> i32 {
    (c as u32 - '0' as u32) as i32
}

解法2：改进型全适应解法

改进的地方

• 使用双栈（数字栈和运算符栈）
• 适用于有括号的表达式
• 适用于+ - * / ^ %的运算符

思路

算法来源：https://leetcode-cn.com/problems/basic-calculator-ii/solution/shi-yong-shuang-zhan-jie-jue-jiu-ji-biao-c65k/

思路一句话总结：模拟人计算表达式的过程，遇到括号先算括号内部的，遇到高优先级的先计算高优先级

思路具体如下：

• 一共有两个栈：数字栈和运算符栈
• (: 直接加入运算符栈中，等待与之匹配的)
• + - * / ^ %: 需要将操作放入运算符栈中。
• 只有「栈内运算符」比「当前运算符」优先级高/同等，才进行运算，（直到没有操作或者遇到左括号），计算结果放到栈中

该算法来源中有个例子，比如当前已读取的运算符为2 + 1（完整的运算符为：2 + 1 * 2）。

1. 如果后面是+ 2或者是- 1，满足「栈内运算符」比「当前运算符」优先级相等或者更高，说明可以直接运算2 + 1然后把结果放入数字栈中
2. 如果后面是* 2或者是/ 1，当前的运算符为*或者/，比栈内运算符+要高，所以要先计算*或者/。即，「栈内运算符」比「当前运算符」低，不能直接运算2 + 1，只能先运算后面1 * 2。

代码

rust代码(v2.rs)如下：

use std::collections::HashMap;

/// Solution: https://leetcode-cn.com/problems/basic-calculator-ii/solution/shi-yong-shuang-zhan-jie-jue-jiu-ji-biao-c65k/
/// PS：v2只能应对`+-*/%^`，甚至可以处理带括号的情况
///
/// 原理：
/// 因为这套「表达式计算」处理逻辑，本质上模拟了人脑的处理逻辑：根据下一位的运算符优先级决定当前运算符是否可以马上计算。
///
/// 改变：未完全按照原solution进行处理，暂时不考虑复杂情况
pub fn calculate(s: String) -> i32 {
    let s = remove_whitespace(&s);
    if s.is_empty() {
        return 0;
    }
    let n = s.len();
    let mut nums_stack: Vec<i32> = vec![];
    let mut ops_stack: Vec<char> = vec![];
    let ops_priority = setup_op_priority();

    let mut i = 0;
    while i < n {
        let c = s.chars().nth(i).unwrap();
        match c {
            '(' => ops_stack.push(c),
            ')' => {
                // 计算到最近一个左括号为止
                while !ops_stack.is_empty() {
                    if ops_stack.last().unwrap() == &'(' {
                        ops_stack.pop();
                        break;
                    }
                    calc(&mut nums_stack, &mut ops_stack);
                }
            }
            '0'..='9' => {
                // 把所有的数字都探测完成，然后压栈保存
                let mut num = 0;
                let mut j = i;
                while j < n && s.chars().nth(j).unwrap().is_numeric() {
                    let j_char = s.chars().nth(j).unwrap();
                    num = num * 10 + parse_as_int(j_char);
                    j += 1;
                }
                i = j - 1;
                nums_stack.push(num);
            }
            _ => {
                // 分支：其他操作符号（无括号的运算符）
                //
                // 有一个新操作要入栈时，先把栈内可以算的都算了
                // 只有满足「栈内运算符」比「当前运算符」优先级高/同等，才进行运算
                while !ops_stack.is_empty() && ops_stack.last().unwrap() != &'(' {
                    let prev_op = ops_stack.last().unwrap();
                    if ops_priority.get(prev_op) >= ops_priority.get(&c) {
                        calc(&mut nums_stack, &mut ops_stack);
                    } else {
                        break;
                    }
                }
                ops_stack.push(c);
            }
        }
        i += 1;
    }

    // 计算剩余的栈中的数据
    while !ops_stack.is_empty() {
        calc(&mut nums_stack, &mut ops_stack);
    }
    // 拿出结果
    nums_stack.pop().unwrap()
}

fn calc(nums_stack: &mut Vec<i32>, ops_stack: &mut Vec<char>) {
    let b = nums_stack.pop().unwrap();
    let a = nums_stack.pop().unwrap();
    let op = ops_stack.pop().unwrap();
    let ans = match op {
        '+' => a + b,
        '-' => a - b,
        '*' => a * b,
        '/' => a / b,
        '%' => a % b,
        '^' => a.pow(b as u32),
        _ => unreachable!(),
    };
    nums_stack.push(ans);
}

fn setup_op_priority() -> HashMap<char, i32> {
    let mut map = HashMap::new();
    map.insert('+', 1);
    map.insert('-', 1);
    map.insert('*', 2);
    map.insert('/', 2);
    map.insert('%', 2);
    map.insert('^', 3);

    map
}

fn parse_as_int(c: char) -> i32 {
    (c as u32 - '0' as u32) as i32
}

fn remove_whitespace(s: &str) -> String {
    s.split_whitespace().collect::<String>()
}