[leetcode] 150。逆ポーランド記法を評価する
150 Evaluate Reverse Polish Notation
説明
逆ポーランド記法で算術式の値を評価します。
有効な演算子は+、-、*、/です。各オペランドは整数または別の式にすることができます。
注意:
- 2つの整数間の除算は、ゼロに向かって切り捨てる必要があります。
- 指定されたRPN式は常に有効です。つまり、式は常に結果に評価され、ゼロ除算演算は行われません。
例1:
Input: ['2', '1', '+', '3', '*'] Output: 9 Explanation: ((2 + 1) * 3) = 9
例2:
Input: ['4', '13', '5', '/', '+'] Output: 6 Explanation: (4 + (13 / 5)) = 6
例3:
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
分析
タイトルの意味は次のとおりです。接尾辞式を指定し、操作の値を見つけます。
- この質問は、スタックによって解決される以前の反ポーランドソリューションと同じです。スタッキングおよびポップ操作の大きな波がありますが、これは比較的単純で簡単です。コードを直接見てください。
コード
class Solution { public: int evalRPN(vector& tokens) { stack s for(auto token: tokens){ if((token[0]>='0'&&token[0]1)){ int num=0 int i=0 int flag=1 if(token[i]=='-'){ flag=-1 i++ } while(token[i]!=' '){ num=num*10+token[i]-'0' i++ } s.push(flag*num) }else if(token[0]=='+'||token[0]=='-'||token[0]=='*'||token[0]=='/'){ int a=s.top() s.pop() int b=s.top() s.pop() int res=0 switch(token[0]){ case '+': res=a+b break case '-': res=b-a break case '*': res=a*b break case '/': res=b/a break } s.push(res) } } return s.top() } }