leetcode 150. Evaluate Reverse Polish Notation 逆波兰表达式的计算

深碍√TFBOYSˉ_ 2022-06-08 06:24 136阅读 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:  
\[“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) 
        {
            if(tokens==null || tokens.length<=0)
                return 0;
            Stack<Integer> myStack=new Stack<>();
            for(int i=0;i<tokens.length;i++)
            {
                String one=tokens[i];
                if(isOperator(one))
                {
                    //记着要a和b的操作数的顺序，对于 整数除法是相关的，这里也不压考虑分母为0的情况
                    int a=myStack.pop();
                    int b=myStack.pop();
                    int res=getRes(b,a,one);
                    myStack.push(res);
                }else
                    myStack.push(Integer.parseInt(one));
            }
            int finRes=myStack.pop();
            return finRes;
        }
    
        public int getRes(int a, int b, String one) 
        {
            one=one.replace(" ", "");
            if(one.equals("+"))
                return (a+b);
            else if(one.equals("-"))
                return (a-b);
            else if(one.equals("*"))
                return (a*b);
            else if(one.equals("/"))
                return (a/b);
            return 0;
        }
        public boolean isOperator(String one) 
        {
            one=one.replace(" ", "");
            if(one.equals("+") || one.equals("-") || one.equals("*") || one.equals("/") )
                return true;
            else
                return false;
        }
    }

下面是C++的做法，就是使用栈做遍历

代码如下：

#include <iostream>
    #include <climits>
    #include <map>
    #include <vector>
    #include <algorithm>
    #include <stack>
    #include <sstream>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int evalRPN(vector<string>& tokens) 
        {
            if (tokens.size() <= 0)
                return 0;
    
            stack<int> skt;
            for (int i = 0; i < tokens.size(); i++)
            {
                if (isOp(tokens[i]))
                {
                    int a = skt.top();
                    skt.pop();
                    int b = skt.top();
                    skt.pop();
                    skt.push(getRes(b, a, tokens[i]));
                }
                else
                {
                    stringstream ss;
                    ss << tokens[i];
                    int a = 0;
                    ss >> a;
                    skt.push(a);
                }
            }
    
            int res = skt.top();
            skt.pop();
            return res;
        }
    
        int getRes(int a, int b, string op)
        {
            if (op == "+")
                return a + b;
            else if (op == "-")
                return a - b;
            else if (op == "*")
                return a * b;
            else if (op == "/")
                return a / b;
            else
                return 0;
        }
        bool isOp(string op)
        {
            if (op == "+" || op == "-" || op == "*" || op == "/")
                return true;
            else
                return false;
        }
    };