后缀表达式求值

class Solution {
public:
    string itoa( int i ) {
        static char buf[30];
        sprintf( buf, "%d", i );
        return string(buf);
    }
    int evalRPN(vector<string> &tokens) {
        stack<string> expr;
        for( int i = 0; i < tokens.size(); ++i ) {
            string str = tokens[i];
            if( str != "+" && str != "-" && str != "*" && str != "/" ) {
                expr.push( str );
                continue;
            }           
            string strb = expr.top(); expr.pop();
            string stra = expr.top(); expr.pop();
            int a = atoi( stra.c_str() ), b = atoi( strb.c_str() );
            if( false ) {}
            else if ( str == string("+") ) { expr.push( itoa(a+b) ); }
            else if ( str == string("-") ) { expr.push( itoa(a-b) ); }
            else if ( str == string("*") ) { expr.push( itoa(a*b) ); }
            else if ( str == string("/") ) { expr.push( itoa(a/b) ); }
        }
        return atoi(expr.top().c_str());
    }
};

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        if( tokens.empty() ) { return 0; }
        if( tokens.size() < 3 ) { return atoi(tokens.back().c_str()); }
        stack<int> s;
        s.push( atoi(tokens[0].c_str()) );
        s.push( atoi(tokens[1].c_str()) );
        for( int i = 2; i < (int)tokens.size(); ++i ) {
            string &t = tokens[i];
            if( t== "+"||t=="-"||t=="*"||t=="/" ) {
                int b = s.top(); s.pop();
                int a = s.top(); s.pop();
                int c;
                if( t == "+" ) {
                    c = a+b;
                } else if( t == "-" ) {
                    c = a-b;
                } else if( t == "*" ) {
                    c = a*b;
                } else {
                    c = a/b;
                }
                s.push( c );
            } else {
                s.push( atoi(tokens[i].c_str()) );
            }
        }
        return s.top();
    }
};

/*
 *为什么我的代码在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;
    }
}

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

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

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

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

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

// 注意入栈和出栈顺序



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

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的，搞不懂

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