[编程题]evaluate-reverse-polish-notati
• 热度指数：114495 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
• 算法知识视频讲解

`  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9↵  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6`
Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are+,-,*,/. Each operand may be an integer or another expression.

Some examples:

`  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9↵  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6`
```import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0;i<tokens.length;i++){
try{
int num = Integer.parseInt(tokens[i]);
}catch (Exception e) {
int b = stack.pop();
int a = stack.pop();
}
}
return stack.pop();
}
private int get(int a,int b,String operator){
switch (operator) {
case "+":
return a+b;
case "-":
return a-b;
case "*":
return a*b;
case "/":
return a/b;
default:
return 0;
}
}
}```

```class Solution {
public:
int evalRPN(vector<string> &tokens) {
stack<int> numbers;
for(auto token : tokens)
{
if(token == "+" || token == "-" || token == "*" || token == "/")
{
int a,b,res;
b=numbers.top();numbers.pop();
a=numbers.top();numbers.pop();
if(token == "+")
res=a+b;
else if(token == "-")
res=a-b;
else if(token == "*")
res=a*b;
else
res=a/b;
numbers.push(res);
}
else
{
stringstream ss;
ss<<token;
int temp;
ss>>temp;
numbers.push(temp);
}
}
return numbers.top();
}
};```

【java】

1.利用stack来计算波兰表达式的值，这都是套路
2.程序鲁棒性，考虑各种可能的异常

1.遇到操作数就出栈，把计算结果入栈
1.1计算结果时，stack至少2个数，否则不合法，返回0
2.遇到数字就入栈
2.1如果不是操作数，也无法转换为数字，就返回0，这里用try catch
3.结果要合法：
3.1如果遍历完成,stack的元素不止1个，说明不合法，返回0
3.2当stack元素只有一个的时候，返回结果
```public int evalRPN(String[] tokens) {
if(tokens == null || tokens.length == 0) return 0;
Stack<Integer> s = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
String cur = tokens[i];
if(cur.equals("+") || cur.equals("-") || cur.equals("*") || cur.equals("/")) {
if(s.size() < 2) return 0;//如果操作数不合法,没有足够的数来操作，返回0
int after = s.pop();
int before = s.pop();
if(cur.equals("+")) {
s.push(before + after);
}else if(cur.equals("-")) {
s.push(before - after);
}else if(cur.equals("*")) {
s.push(before * after);
}else if(cur.equals("/")) {
s.push(before / after);
}
} else {//不是操作数
try {
int num = Integer.parseInt(cur);// 非法字符返回0
s.push(num);
} catch (NumberFormatException e) {
return 0;
}
}
}
return s.size() == 1 ? s.pop() : 0;//结果要合法
}
```

```/*
*为什么我的代码在IDE上运行正常，但是在网站上提交的时候会报错，
*提示java.lang.NumberFormatException: For input string: "/"
*测试用例是{"0", "3", "/"}
*问题解决： if语句判断中tokens[i] == "+" 修改为tokens[i].equals("+")
*/```
```import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> num = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
if (tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/")) {
int num2 = num.pop();
int num1 = num.pop();
num.push(calculate(tokens[i], num1, num2));
} else {
int number = Integer.parseInt(tokens[i]);
num.push(number);
}
}
return num.pop();
}

private int calculate(String op, int f1, int f2) {
if (op.equals("+")) {
return f1 + f2;
}
if (op.equals("-")) {
return f1 - f2;
}
if (op.equals("*")) {
return f1 * f2;
}
if (op.equals("/")) {
return f1 / f2;
}
throw new RuntimeException(op + " is not supported");
}
}```

```package go.jacob.day0526.stackqueue;

import java.util.Stack;

/**
* Evaluate the value of an arithmetic expression in Reverse Polish Notation.
* <p>
* Valid operators are +, -, *, /. Each operand may be an integer or another expression.
* <p>
* Note:
* <p>
* Division between two integers should truncate toward zero.
* The given RPN expression is always valid.
* That means the expression would always evaluate to a result and there won't be any divide by zero operation.
* Example 1:
* <p>
* Input: ["2", "1", "+", "3", "*"]
* Output: 9
* Explanation: ((2 + 1) * 3) = 9
* Example 2:
* <p>
* Input: ["4", "13", "5", "/", "+"]
* Output: 6
* Explanation: (4 + (13 / 5)) = 6
* Example 3:
* <p>
* Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
* Output: 22
* Explanation:
* ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
* = ((10 * (6 / (12 * -11))) + 17) + 5
* = ((10 * (6 / -132)) + 17) + 5
* = ((10 * 0) + 17) + 5
* = (0 + 17) + 5
* = 17 + 5
* = 22
* <p>
* 非常典型的一类用栈来解决的问题
* 模拟四则运算
* 这道题还比较简单，没有涉及到括号
*/
public class P150_EvaluateReversePolishNotation {

public static int evalRPN(String[] tokens) {
if (tokens == null || tokens.length == 0)
return 0;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < tokens.length; i++) {
if (tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/")) {
int x = stack.pop();
int y = stack.pop();
stack.push(calculate(y, x, tokens[i]));
} else
stack.push(Integer.parseInt(tokens[i]));

}

return stack.pop();
}

private static Integer calculate(int x, int y, String token) {
if (token.equals("+"))
return x + y;
else if (token.equals("-"))
return x - y;
else if (token.equals("*"))
return x * y;
else
return x / y;
}
}

```

```/**
＊
*  1.这种逆波兰表达式，很明显，用栈求解。
*  2.需要注意的一点，就是来一个新的符号的时候，将栈中的两个值取出进行操作，再放回栈中。
*    此时先取出的为num2,后取出的为num1，进行num1 (+-/*) num2 操作
*
**/

class Solution {
public:
int evalRPN(vector<string> &tokens) {
if(tokens.size() == 0)
return 0;
stack<int> st;
for(int i = 0; i < tokens.size(); ++i)
{
string s = tokens[i];
if(s == "+" || s == "-" || s == "*" || s == "/")
{
if(st.size() < 2)
return 0;
int num2 = st.top(); st.pop();
int num1 = st.top(); st.pop();
int result = 0;

if(s == "+")
result = num1 + num2;
else if(s == "-")
result = num1 - num2;
else if(s == "*")
result = num1 * num2;
else if(s == "/")
result = num1 / num2;
st.push(result);
}
else
{
st.push(atoi(s.c_str()));
}
}
return st.top();
}
};```

``````//stack实现 注意-和/的时候 是操作数换一换
public int evalRPN(String[] tokens) {
if(tokens.length<1)
return 0;
Stack<Integer> stack =new Stack<>();
for(int i=0;i<tokens.length;i++){
if(tokens[i].equals("+")){
int num1=stack.pop();
int num2=stack.pop();
stack.push(num1+num2);
}
else if(tokens[i].equals("*")){
int num1=stack.pop();
int num2=stack.pop();
stack.push(num1*num2);
}
else if(tokens[i].equals("/")){
int num1=stack.pop();
int num2=stack.pop();
stack.push(num2/num1);
}
else if(tokens[i].equals("-")){
int num1=stack.pop();
int num2=stack.pop();
stack.push(num2-num1);
}
else{
stack.push(Integer.parseInt(tokens[i]));
}
}
return stack.pop();
}
``````

import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
Stack s = new Stack();
int length = tokens.length - 1;
int i = 0;
while(i<=length){
if( tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/") ){
int sec = Integer.parseInt(s.pop().toString());
int fir = Integer.parseInt(s.pop().toString());
if(tokens[i].equals("+"))
s.push(fir + sec);
else if(tokens[i].equals("-"))
s.push(fir - sec);
else if(tokens[i].equals("*"))
s.push(fir * sec);
else s.push(fir / sec);
}else{
s.push(tokens[i]);
}
i++;
}
return Integer.parseInt(s.pop().toString());
}
}

```import java.util.*;
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> s = new Stack<Integer>();
for(int i = 0;i<tokens.length;i++){
switch(tokens[i]){
case "+":
s.push(s.pop() + s.pop());
break;
case "-":
int num1 = s.pop();
int num2 = s.pop();
s.push(num2-num1);
break;
case "*":
s.push(s.pop() * s.pop());
break;
case "/":
int num3 = s.pop();
int num4 = s.pop();
s.push(num4/num3);
break;
default:
s.push(Integer.parseInt(tokens[i]));
}
}
return s.pop();
}
}```

```class Solution {
public:
int evalRPN(vector<string> &tokens) {
stack<int> ista;
for(int i = 0; i < tokens.size(); i++){
if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){
int temp = 0;
int a = ista.top();ista.pop();
int b = ista.top();ista.pop();
if(tokens[i] == "+"){
temp = b + a;
}else if(tokens[i] == "-"){
temp = b - a;
}else if(tokens[i] == "*"){
temp = b * a;
}else{
temp = b / a;
}
ista.push(temp);
}else{
ista.push(atoi(tokens[i].c_str()));
}
}
return ista.top();
}
};```

```import java.util.ArrayList;

public class Solution {
public int evalRPN(String[] tokens) {
ArrayList<Integer> list = new ArrayList<Integer>();
for (String e : tokens){
switch (e){
case "+":
list.add(list.remove(list.size() - 2) + list.remove(list.size() - 1));
break;
case "-":
list.add(list.remove(list.size() - 2) - list.remove(list.size() - 1));
break;
case "*":
list.add(list.remove(list.size() - 2) * list.remove(list.size() - 1));
break;
case "/":
list.add(list.remove(list.size() - 2) / list.remove(list.size() - 1));
break;
default:
break;
}
}
return list.get(0);
}
}```

```import java.util.*;
public class Solution {
public int evalRPN(String[] tokens) {
Stack stack=new Stack();
int length=tokens.length;
for(int i=0;i<length;i++){
if(check(tokens[i])){
int num=change(tokens[i]);
stack.push(num);
}else{
int preNum=(int)stack.pop();
int bacNum=(int)stack.pop();
int res=calc(bacNum,tokens[i],preNum);
stack.push(res);
}
}
return (int)stack.pop();
}
public boolean check(String str){
boolean isNumber=true;
if(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")){
isNumber=false;
}
return isNumber;
}
public int change(String str){
return Integer.valueOf(str);
}
public int calc(int a,String ch,int b){
if(ch.equals("+")) return a+b;
else if(ch.equals("-")) return a-b;
else if(ch.equals("*")) return a*b;
else return a/b;
}
}```

```// 注意入栈和出栈顺序

class Solution {
public:
int evalRPN(vector<string> &tokens) {
stack<int> s;
int result;
for(int i = 0; i < tokens.size(); i++){
string str = tokens[i];
if(str == "*" || str == "-" || str == "+" || str == "/"){
int value2 = s.top(); s.pop();
int value1 = s.top(); s.pop();
if(str == "*"){
result = value1 * value2;
}else if(str == "/"){
result = value1 / value2;
}else if(str == "+"){
result = value1 + value2;
}else{
result = value1 - value2;
}
s.push(result);
}else{
s.push(stoi(str));
}
}
return s.top();
}
}```

```class Solution {
public:
typedef enum  {
Symbol_Plus,
Symbol_Minus,
Symbol_multi,
Symbol_Divi,
Number
} char_style;

char_style JudgeInputChar(const string& input_string) {

if (input_string == "+")
return Symbol_Plus;
else if (input_string == "-")
return Symbol_Minus;
else if (input_string == "*")
return Symbol_multi;
else if (input_string == "/")
return Symbol_Divi;
else return Number;
}

int evalRPN(vector<string> &tokens) {
if (tokens.size() == 0)
return 0;
stack<int> number_stack;
for (string c : tokens) {
if (JudgeInputChar(c) == Number)
number_stack.push(atoi(c.c_str()));
else {
int a1 = number_stack.top();
number_stack.pop();
int a2 = number_stack.top();
number_stack.pop();
int result;
if (JudgeInputChar(c) == Symbol_Plus) {
result = a1 + a2;
} else if (JudgeInputChar(c) == Symbol_Minus) {
result = a2 - a1;
} else if (JudgeInputChar(c) == Symbol_multi) {
result = a2 * a1;
} else if (JudgeInputChar(c) == Symbol_Divi) {
result = a2 / a1;
}
number_stack.push(result);
}
}
return number_stack.top();
}
};```

```package leetcode;

import java.util.Stack;

/**
* @ClassName EvalRPN
* @Description
* 计算逆波兰式（后缀表达式）的值
* 运算符仅包含“ +”，“ - ”，“*”和“/”，***作数可能是整数或其他表达式
* 例如：
*    [“2”，“1”，“+”，“3”，“*”]  - >（（2 + 1）* 3） - >9↵[“4”，“13”，“5”，“ /“，”+“]  - >（4 +（13/5）） - > 6
* 在反向波兰表示法中计算算术表达式的值  。
* 有效的运算符是+， - ，*，/。每个操作数可以是整数或另一个表达式。
*
* 一些例子：
*
*   [“2”，“1”，“+”，“3”，“*”]  - >（（2 + 1）* 3） - >9↵[“4”，“13”，“5”，“ /“，”+“]  - >（4 +（13/5）） - > 6
* @Author Wlison
* @Date 2019/8/26 20:36
* @Version 1.0
**/
public class EvalRPN {

//test
public static void main(String[] args) {
String[] str = {"4", "13", "5", "/", "+"};
System.out.println(new EvalRPN().evalRPN(str));
}

public  int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
String opt = "+-*/";
for (int i = 0; i < tokens.length; i++) {
if(!opt.contains(tokens[i])){
stack.push(Integer.valueOf(tokens[i]));
}else{
int b = Integer.valueOf(stack.pop());
int a = Integer.valueOf(stack.pop());
int operate = getOperate(a, b, opt.indexOf(tokens[i]));
stack.push(operate);
}
}
return stack.pop();
}
public  int getOperate(int a,int b,int opt){
switch (opt){
case 0:return a+b;
case 1:return a-b;
case 2:return a*b;
case 3:return a/b;
default:return 0;
}
}
}
```

import java.util.Stack;
public class Solution {
public int evalRPN（String [] tokens）{
if（tokens == null）return 0;
Stack <Integer> stack = new Stack <>（）;
整数a = 0;
整数b = 0;
for（String str：tokens）
{
if（“+”。equals（str）||“ - ”。equals（str）||“*”。equals（str）||“/”。equals（str））
{
a = stack.pop（）;
b = stack.pop（）;
}
if（“+”。equals（str））stack.push（b + a）;
else if（“ - ”。equals（str））stack.push（ba）;
否则如果（“*”。
else if（“/”。equals（str））stack.push（b / a）;
else stack.push（new Integer（str））;
}
return stack.pop（）;
}
}

``````public int evalRPN(String[] tokens) {
Stack<Integer> numStack = new Stack<>();
int length = tokens.length;
String handlingChar;
for (int i = 0; i < length; i++) {
handlingChar = tokens[i];
switch (handlingChar){
case "+":
numStack.push(numStack.pop() + numStack.pop());
break;
case "-":
Integer subtrahend = numStack.pop();
numStack.push(numStack.pop() - subtrahend);
break;
case "*":
numStack.push(numStack.pop() * numStack.pop());
break;
case "/":
Integer divisor = numStack.pop();
numStack.push(numStack.pop() / divisor);
break;
default:
numStack.push(new Integer(handlingChar));
}
}
return numStack.pop();
}``````

```class Solution {
public:
int evalRPN(vector<string> &tokens) {
int res = 0;
stack<int> stk;
int len = tokens.size();
if(!len) return res;
int num1, num2;
for(int i=0;i<len;++i)
{
try
{
stk.push(stoi(tokens[i]));
}
catch(invalid_argument) // 或者exception
{
num1 = stk.top(), stk.pop();
num2 = stk.top(), stk.pop();
if(tokens[i]=="+") stk.push(num1+num2);
else if(tokens[i]=="-") stk.push(num2-num1);
else if(tokens[i]=="*") stk.push(num1*num2);
else stk.push(num2/num1);
}
}
return stk.empty() ? 0 : stk.top();
}
};
```

```import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
//当给定字符串为空或者字符串长度为0时，返回0
if(tokens == null || tokens.length == 0) return 0;
//new一个栈，用于存放中间过程的计算结果
Stack<Integer> stack = new Stack<Integer>();
for(int i = 0;i<tokens.length;i++){
try{
//将String字符类型数据转换为Integer整型数据
//遇到一些不能被转换为整型的字符时，会抛出异常
int num = Integer.parseInt(tokens[i]);
//将tokens[i]位置数据添加到栈中
}catch (Exception e) {
//如果操作数不合法,没有足够的数来操作，返回0
if(stack.size() < 2) return 0;
int b = stack.pop();
int a = stack.pop();
//对a,b两个元素进行运算，并将结果添加到栈中
}
}
//将最终的结果返回
return stack.pop();
}
//定义a,b两元素计算的方法
private int get(int a,int b,String operator){
switch (operator) {
//加法
case "+":            return a+b;
//减法
case "-":            return a-b;
//乘法
case "*":            return a*b;
//除法，返回的是商
case "/":            return a/b;
default:            return 0;
}
}
}```

## 题目描述

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are+,-,*,/. Each operand may be an integer or another expression.
Some examples: ## 提交代码

``````import java.util.Stack;
public class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
int res = 0;
if(tokens == null || tokens.length <= 0){
return res;
}
if(tokens.length == 1){
res = Integer.valueOf(tokens);
}
for(String str:tokens){
if(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")){
int v1 = stack.pop();
int v2 = stack.pop();
if(str.equals("+")){
res = v1+v2;
}else if(str.equals("-")){
res = v2-v1;
}else if(str.equals("*")){
res = v1*v2;
}else if(str.equals("/")){
res = v2/v1;
}
stack.push(res);
}else{
stack.push(Integer.valueOf(str));
}
}
return res;
}
}``````

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题