Go Deep | Blog

Go Deep and Be professional

0%

Rust版Basic Calculator II以及改进

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

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

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

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

题目描述

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

题目描述:

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

  • 示例 1:

    1
    2
    输入:s = "3+2*2"
    输出:7
  • 示例 2:

    1
    2
    输入:s = " 3/2 "
    输出:1
  • 示例 3:

    1
    2
    输入: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)如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/// 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)如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
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>()
}

End