Skip to content

Commit 3efe9d8

Browse files
JavaCodeMingJavaCodeMing
committed
Create 150.逆波兰表达式求值(中等).md
1 parent 3a49f47 commit 3efe9d8

1 file changed

Lines changed: 94 additions & 0 deletions

File tree

‎Algorithm/150.逆波兰表达式求值(中等).md‎

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
```text
2+
题目: 根据逆波兰表示法,求表达式的值
3+
有效的运算符包括 +, -, *, / ;每个运算对象可以是整数,也可以是另一个逆波兰表达式;
4+
说明:
5+
整数除法只保留整数部分;
6+
给定逆波兰表达式总是有效的;换句话说,表达式总会得出有效数值且不存在除数为0的情况;
7+
示例:
8+
输入: ["2", "1", "+", "3", "*"]
9+
输出: 9
10+
解释: 该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9
11+
1.栈:
12+
[1]思路:
13+
(1)遍历给定的字符串数组,如果不是运算符则入栈
14+
(2)如果遍历到的是运算符,则从栈中取出两个值,按运算符的类型进行运算
15+
(3)再将运算得到的值添加到栈中,直到最后,栈中留下的就是最终的结果
16+
[2]实现:
17+
public int evalRPN(String[] tokens) {
18+
Map<String,Integer> map = new HashMap<>();
19+
map.put("+",1);
20+
map.put("-",2);
21+
map.put("*",3);
22+
map.put("/",4);
23+
// 定义栈
24+
Deque<Integer> stack = new ArrayDeque<>();
25+
// 遍历
26+
for (String token : tokens) {
27+
if(map.containsKey(token)){
28+
// 遍历到的是运算符
29+
Integer second = stack.pop();
30+
Integer first = stack.pop();
31+
switch (map.get(token)){
32+
case 1:
33+
stack.push(first+second);
34+
break;
35+
case 2:
36+
stack.push(first-second);
37+
break;
38+
case 3:
39+
stack.push(first*second);
40+
break;
41+
case 4:
42+
stack.push(first/second);
43+
break;
44+
default:
45+
}
46+
}else {
47+
// 遍历到的不是运算符
48+
stack.push(Integer.valueOf(token));
49+
}
50+
}
51+
return stack.pop();
52+
}
53+
[3]复杂度分析:
54+
(1)时间复杂度: O(N),其中N为给定字符串数组的长度
55+
(2)空间复杂度: O(N),最坏的情况下,所有的数字都在前面,运算符都在后面,则栈中最多需要存储N/2+1个数
56+
2.纯数组模拟栈:
57+
[1]思路: 使用纯数组模拟栈来实现
58+
(1)定义长度为N/2+1的数组,因最坏情况下,所有的数值都在前面,则此时需要存储N/2+1个值(数值比运算符多一个);
59+
(2)使用一个数组下标变量index来操作数组中的值,每次计算时,对index-2的位置的值进行计算,并把下标移动到index-1
60+
[2]实现:
61+
class Solution {
62+
public int evalRPN(String[] tokens) {
63+
int[] numStackf = new int[tokens.length/2+1];
64+
int index = 0;
65+
for (String token : tokens) {
66+
// 根据遍历到的字符串做相应的操作
67+
switch (token){
68+
case "+":
69+
// 移动到倒数第二个值的位置,再与倒数第一个位置的值进行相加
70+
// 此时倒数第一个位置上的值就被废弃,将数组下标变量移动到该位置,之后添加值时会被覆盖
71+
numStackf[index-2] += numStackf[--index];
72+
break;
73+
case "-":
74+
numStackf[index-2] -= numStackf[--index];
75+
break;
76+
case "*":
77+
numStackf[index-2] *= numStackf[--index];
78+
break;
79+
case "/":
80+
numStackf[index-2] /= numStackf[--index];
81+
break;
82+
default:
83+
// 默认情况下是往数组中添加值
84+
numStackf[index++] = Integer.parseInt(token);
85+
}
86+
}
87+
// 当计算完毕,数组中第一个位置的值就是最后计算的结果(和使用栈的方式类似)
88+
return numStackf[0];
89+
}
90+
}
91+
[3]复杂度分析:
92+
(1)时间复杂度: O(N),其中N为给定字符串数组的长度
93+
(2)空间复杂度: O(N),需按最坏的情况,分配给数组N/2+1的长度
94+
```

0 commit comments

Comments
 (0)