Skip to content

Commit 6d66791

Browse files
yanglbmeyanglbme
committed
feat: add python and java solutions to leetcode problem: No.0150
See https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
1 parent 0d436da commit 6d66791

File tree

6 files changed

+149
-44
lines changed

6 files changed

+149
-44
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,6 +97,7 @@
9797
1. [最小栈](/solution/0100-0199/0155.Min%20Stack/README.md)
9898
1. [用栈实现队列](/solution/0200-0299/0232.Implement%20Queue%20using%20Stacks/README.md)
9999
1. [用队列实现栈](/solution/0200-0299/0225.Implement%20Stack%20using%20Queues/README.md)
100+
1. [逆波兰表达式求值](/solution/0100-0199/0150.Evaluate%20Reverse%20Polish%20Notation/README.md)
100101

101102
### 动态规划
102103

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -92,6 +92,7 @@ Complete solutions to [LeetCode](https://leetcode-cn.com/problemset/all/), [LCOF
9292
1. [Min Stack](/solution/0100-0199/0155.Min%20Stack/README_EN.md)
9393
1. [Implement Queue using Stacks](/solution/0200-0299/0232.Implement%20Queue%20using%20Stacks/README_EN.md)
9494
1. [Implement Stack using Queues](/solution/0200-0299/0225.Implement%20Stack%20using%20Queues/README_EN.md)
95+
1. [Evaluate Reverse Polish Notation](/solution/0100-0199/0150.Evaluate%20Reverse%20Polish%20Notation/README_EN.md)
9596

9697
### Dynamic Programming
9798

‎solution/0100-0199/0150.Evaluate Reverse Polish Notation/README.md

Lines changed: 56 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -47,22 +47,76 @@
4747

4848
<!-- 这里可写通用的实现逻辑 -->
4949

50+
栈实现。
51+
52+
遍历数组，遇到数字则压入栈中，遇到运算符号，则从栈中弹出右、左操作数，运算过后，将结果压入栈中。
53+
54+
遍历结束后，返回栈中的唯一元素。
55+
5056
<!-- tabs:start -->
5157

5258
### **Python3**
5359

5460
<!-- 这里可写当前语言的特殊实现逻辑 -->
5561

5662
```python
57-
63+
import operator
64+
65+
class Solution:
66+
def evalRPN(self, tokens: List[str]) -> int:
67+
opt = {
68+
"+": operator.add,
69+
"-": operator.sub,
70+
"*": operator.mul,
71+
"/": operator.truediv
72+
}
73+
s = []
74+
for token in tokens:
75+
if token in opt:
76+
s.append(int(opt[token](s.pop(-2), s.pop(-1))))
77+
else:
78+
s.append(int(token))
79+
return s[0]
5880
```
5981

6082
### **Java**
6183

6284
<!-- 这里可写当前语言的特殊实现逻辑 -->
6385

6486
```java
65-
87+
class Solution {
88+
public int evalRPN(String[] tokens) {
89+
Deque<Integer> s = new ArrayDeque<>();
90+
int left, right;
91+
for (String token : tokens) {
92+
switch(token) {
93+
case "+":
94+
right = s.pop();
95+
left = s.pop();
96+
s.push(left + right);
97+
break;
98+
case "-":
99+
right = s.pop();
100+
left = s.pop();
101+
s.push(left - right);
102+
break;
103+
case "*":
104+
right = s.pop();
105+
left = s.pop();
106+
s.push(left * right);
107+
break;
108+
case "/":
109+
right = s.pop();
110+
left = s.pop();
111+
s.push(left / right);
112+
break;
113+
default:
114+
s.push(Integer.valueOf(token));
115+
}
116+
}
117+
return s.pop();
118+
}
119+
}
66120
```
67121

68122
### **...**

‎solution/0100-0199/0150.Evaluate Reverse Polish Notation/README_EN.md

Lines changed: 50 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -72,13 +72,61 @@
7272
### **Python3**
7373

7474
```python
75-
75+
import operator
76+
77+
class Solution:
78+
def evalRPN(self, tokens: List[str]) -> int:
79+
opt = {
80+
"+": operator.add,
81+
"-": operator.sub,
82+
"*": operator.mul,
83+
"/": operator.truediv
84+
}
85+
s = []
86+
for token in tokens:
87+
if token in opt:
88+
s.append(int(opt[token](s.pop(-2), s.pop(-1))))
89+
else:
90+
s.append(int(token))
91+
return s[0]
7692
```
7793

7894
### **Java**
7995

8096
```java
81-
97+
class Solution {
98+
public int evalRPN(String[] tokens) {
99+
Deque<Integer> s = new ArrayDeque<>();
100+
int left, right;
101+
for (String token : tokens) {
102+
switch(token) {
103+
case "+":
104+
right = s.pop();
105+
left = s.pop();
106+
s.push(left + right);
107+
break;
108+
case "-":
109+
right = s.pop();
110+
left = s.pop();
111+
s.push(left - right);
112+
break;
113+
case "*":
114+
right = s.pop();
115+
left = s.pop();
116+
s.push(left * right);
117+
break;
118+
case "/":
119+
right = s.pop();
120+
left = s.pop();
121+
s.push(left / right);
122+
break;
123+
default:
124+
s.push(Integer.valueOf(token));
125+
}
126+
}
127+
return s.pop();
128+
}
129+
}
82130
```
83131

84132
### **...**

‎solution/0100-0199/0150.Evaluate Reverse Polish Notation/Solution.java

Lines changed: 27 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -1,31 +1,33 @@
11
class Solution {
22
public int evalRPN(String[] tokens) {
3-
Stack<Integer> stack = new Stack<>();
4-
for (String e : tokens) {
5-
if (isNum(e)) {
6-
stack.push(Integer.parseInt(e));
7-
} else {
8-
int y = stack.pop();
9-
int x = stack.pop();
10-
int z = 0;
11-
switch (e) {
12-
case "+": z = x + y; break;
13-
case "-": z = x - y; break;
14-
case "*": z = x * y; break;
15-
case "/": z = x / y; break;
16-
}
17-
stack.push(z);
3+
Deque<Integer> s = new ArrayDeque<>();
4+
int left, right;
5+
for (String token : tokens) {
6+
switch(token) {
7+
case "+":
8+
right = s.pop();
9+
left = s.pop();
10+
s.push(left + right);
11+
break;
12+
case "-":
13+
right = s.pop();
14+
left = s.pop();
15+
s.push(left - right);
16+
break;
17+
case "*":
18+
right = s.pop();
19+
left = s.pop();
20+
s.push(left * right);
21+
break;
22+
case "/":
23+
right = s.pop();
24+
left = s.pop();
25+
s.push(left / right);
26+
break;
27+
default:
28+
s.push(Integer.valueOf(token));
1829
}
1930
}
20-
return stack.peek();
21-
}
22-
23-
private boolean isNum(String val) {
24-
try {
25-
Integer.parseInt(val);
26-
return true;
27-
} catch (Exception e) {
28-
return false;
29-
}
31+
return s.pop();
3032
}
3133
}

‎solution/0100-0199/0150.Evaluate Reverse Polish Notation/Solution.py

Lines changed: 14 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,17 @@
1-
import operator as op
1+
import operator
22

33
class Solution:
4-
def evalRPN(self, tokens):
5-
"""
6-
:type tokens: list[str]
7-
:rtype: int
8-
"""
9-
stack = []
10-
Opr = {"+":op.add, "-":op.sub, "*":op.mul, "/":op.truediv}
11-
12-
for i in tokens:
13-
if i in Opr:
14-
stack.append( int( Opr[i](stack.pop(-2), stack.pop(-1)) ) )
4+
def evalRPN(self, tokens: List[str]) -> int:
5+
opt = {
6+
"+": operator.add,
7+
"-": operator.sub,
8+
"*": operator.mul,
9+
"/": operator.truediv
10+
}
11+
s = []
12+
for token in tokens:
13+
if token in opt:
14+
s.append(int(opt[token](s.pop(-2), s.pop(-1))))
1515
else:
16-
stack.append(int(i))
17-
18-
return stack[0]
16+
s.append(int(token))
17+
return s[0]

0 commit comments

Comments
 (0)