首页 > 试题广场 > evaluate-reverse-polish-notati
[编程题]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]);
				stack.add(num);
			}catch (Exception e) {
				int b = stack.pop();
				int a = stack.pop();
				stack.add(get(a, b, tokens[i]));
			}
		}
		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;
		}
	}
}

发表于 2016-05-29 21:51:50 回复(61)
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();
    }
};

发表于 2016-07-19 00:16:57 回复(15)
【java】
这一题的考点有2个
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;//结果要合法
    }

发表于 2018-06-21 09:24:40 回复(3)
/*
 *为什么我的代码在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");
    }
}

编辑于 2017-07-26 18:21:14 回复(13)
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;
    }
}

















发表于 2018-05-26 19:20:16 回复(0)
/**
 *
 *  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();
    }
};

发表于 2016-08-25 14:39:36 回复(1)
//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();
    }
发表于 2017-11-15 21:36:34 回复(0)
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());  
    }
}
发表于 2017-03-30 17:42:24 回复(1)
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();
    }
}

发表于 2016-06-24 15:53:57 回复(2)
用个栈就可以了
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();
    }
};

发表于 2016-08-23 15:11:20 回复(4)
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:
                    list.add(Integer.valueOf(e));
                    break;
            }
        }
        return list.get(0);
    }
}


发表于 2019-12-31 18:28:53 回复(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;
    }
}

注意,程序代码要注意解离耦合度,这点很重要。虽然会增加代码量,但是会大大提升代码的可读性
发表于 2019-10-21 16:51:48 回复(0)
// 注意入栈和出栈顺序



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();
    }
}

发表于 2019-10-05 07:05:37 回复(0)
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();
}
};

发表于 2019-09-14 20:26:23 回复(0)
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;
        }
    }
}

发表于 2019-08-26 21:48:40 回复(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();
    }
}

发表于 2019-07-10 19:19:43 回复(0)
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();
    }

我想用switch应该挺快的了吧……为什么有人四重判断还能跑30s的,搞不懂

发表于 2019-05-10 20:48:08 回复(0)
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();
    }
};

发表于 2019-05-03 14:28:13 回复(0)
利用try...catch...进行,Poland公式计算明显会用到
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]位置数据添加到栈中
                stack.add(num);              
             }catch (Exception e) { 
                //如果操作数不合法,没有足够的数来操作,返回0
                if(stack.size() < 2) return 0;
                int b = stack.pop();                  
                int a = stack.pop(); 
                //对a,b两个元素进行运算,并将结果添加到栈中
                stack.add(get(a, b, tokens[i]));              
             }          
        }
        //将最终的结果返回
        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;          
        }      
    }  
}

编辑于 2019-04-16 16:38:50 回复(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:

image

解题思路

这一题提示信息是用栈来实现,那么思路为:如果当前元素是数字就入栈,否则就是运算符,那么就将这个运算符前面两个数字进行相应操作,并且将这个操作结果重新再放入栈中,参与下一次的运算。

提交代码

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[0]);
        }
        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;
    }
}
发表于 2019-03-20 11:45:24 回复(0)