iT邦幫忙

1

資結經典題目: 用stack計算逆波蘭表達式

參考題目: 150. Evaluate Reverse Polish Notation

逆波蘭表達式是不必用括號也可以正確計算四則運算順序的一種神奇表達式,
例如說一般日常用的四則運算: 5 - 3 * 2
加上括號5 - (3 * 2)(5 - 3) * 2即是不同的意思。

但若是表達成逆波蘭表達式則不必事先知道哪個運算符號要優先計算

計算方法:
例如有一個逆波蘭表達式5 4 3 * - 2 +
從左到右掃一遍5 4 3 * - 2 +
如果看到數字就把數字丟進stack裡面,
如果碰到運算符號,
就把stack前兩個數字抓出來做運算再丟回stack裡面

程式實作:

class Solution {
public:
    int evalOP(int x, int y, string op){
        if(op=="+"){
            return x+y;
        }
        if(op=="-"){
            return x-y;
        }
        if(op=="*"){
            return x*y;
        }
        if(op=="/"){
            return x/y;
        }
        return 0;
    }
    int evalRPN(vector<string>& tokens) {
        set<string> ops= {"/", "+", "-", "*"};
        stack<int> evalStack;
        for(string token: tokens){
            if(ops.find(token)!=ops.end()){
                int x = evalStack.top();
                evalStack.pop();
                int y = evalStack.top();        
                evalStack.pop();
                evalStack.push(evalOP(y, x, token));
            }
            else{
                evalStack.push(atoi(token.c_str()));
            }
        }
        return evalStack.top();
    }
};

尚未有邦友留言

立即登入留言