首页 > 试题广场 >

后缀表达式求值

[编程题]后缀表达式求值
  • 热度指数:132705 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
计算逆波兰式(后缀表达式)的值
运算符仅包含"+","-","*"和"/",被操作数是整数

保证表达式合法,除法时向下取整。

数据范围:表达式的长度满足:
进阶:空间复杂度 , 时间复杂度
例如:
  ["20", "10", "+", "30", "*"] -> ((20 + 10) * 30) -> 900
  ["40", "130", "50", "/", "+"] -> (40 + (130 / 50)) -> 42
示例1

输入

["20","10","+","30","*"]

输出

900
示例2

输入

["20"]

输出

20
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 回复(63)
【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)
//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)
我真的无语了,这个错在哪里?
      function evalRPN(tokens) {
            // write code here
            const stack = [];
            for (let i = 0; i < tokens.length; i++) {
                const d = tokens[i];
                if (isNaN(d)) {
                    let n2 = stack.pop();
                    let n1 = stack.pop();
                    switch (d) {
                        case '+':
                            stack.push(n1 + n2)
                            break;
                        case '-':
                            stack.push(n1 - n2)

                            break;
                        case '*':
                            stack.push(n1 * n2)
                            break;
                        case '/':
                            stack.push(Math.floor(n1 / n2))
                            break;
                        default:
                            break;
                    }
                } else {
                    stack.push(parseInt(d));
                }
            }
            return stack.pop()
        }


发表于 2022-07-12 14:07:18 回复(0)
int evalRPN(vector<string>& tokens) {
        vector<int> data;
        for(int i=0;i<tokens.size();i++){
            int size=data.size();
            if(tokens[i]=="+")
                data.push_back(data[size-2]+data[size-1]);                                          
            else if(tokens[i]=="-")
                data.push_back(data[size-2]-data[size-1]);                                          
            else if(tokens[i]=="*")
                 data.push_back(data[size-2]*data[size-1]);                                          
            else if(tokens[i]=="/")
                data.push_back(data[size-2]/data[size-1]);
            else{
                data.push_back(atoi(tokens[i].c_str()));
                continue;
            }
            data.erase(data.begin()+size-2,data.erase(data.begin()+size-1));    
        }
        return data[0];
    }
发表于 2021-03-16 13:52:27 回复(0)
class Solution {
public:
    
    int getNum(string s)
    {
        int v = 0, f = 1; 
        for(char c : s) 
        {
            if(c == '-') f = -1;  
            else v = v*10 + c-'0';
        }
        return v*f; 
    }
    
    int evalRPN(vector<string>& tokens) 
    {
        stack<int> s; 
        for(string x : tokens) 
        {
            if(x == "+" || x == "-" || x == "*" || x == "/")
            {
                int n2 = s.top(); s.pop(); 
                int n1 = s.top(); s.pop(); 
                if(x[0] == '+') s.push(n1+n2); 
                else if(x[0] == '-') s.push(n1-n2); 
                else if(x[0] == '*') s.push(n1*n2); 
                else if(x[0] == '/') s.push(n1/n2); 
            }
            else s.push(getNum(x)); 
        }
        return s.top(); 
    }
};

发表于 2021-01-24 22:05:01 回复(0)
import java.util.*;
public class Solution {
    /**
     * 
     * @param tokens string字符串一维数组 
     * @return int整型
     */
    public int evalRPN (String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for(String s : tokens) {
            if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
                int b = stack.pop();
                int a = stack.pop();
                switch(s) {
                    case "+":stack.push(a + b);break;
                    case "-":stack.push(a - b);break;
                    case "*":stack.push(a * b);break;
                    case "/":stack.push(a / b);break;
                }
            }else {
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }
}

发表于 2020-11-28 12:57:27 回复(0)
 public int evalRPN (String[] tokens) {
        // write code here
        if(tokens == null || tokens.length == 0){
            return 0;
        }

        ArrayList<String> sign = new ArrayList<String>(){{
            add("+");
            add("-");
            add("*");
            add("/");
        }};
        Stack<String> stack = new Stack<>();
        for(String ele : tokens){
            if(!sign.contains(ele)){
                stack.push(ele);
            }else {
                int res = 0;
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                if(ele.equals("+")){
                    res = num1 + num2;
                }else if(ele.equals("-")){
                    res = num1 - num2;
                }else if(ele.equals("*")){
                    res = num1 * num2;
                }else if(ele.equals("/")){
                    res = num1 /num2;
                }else {
                    res = 0;
                }
                stack.push("" + res);
            }
        }
        return Integer.parseInt(stack.pop());
    }

发表于 2020-07-13 18:49:30 回复(0)
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)