題目
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 Subscribe to see which companies asked this question.
思路
用棧的出入來模擬后綴表達式的計算，注意入參合法性，除法時除數不能為0等場景
代碼
class Solution {public: bool isOperatorAndLegal(stack<int> &calStack,string &inputString) { if(calStack.size() < 2) { return false; } //長度不滿足運算符要求 if(inputString.size() != 1) { return false; } //不是合法運算符 char operatorChar = inputString.at(0); if(operatorChar != '+' && operatorChar != '-' && operatorChar != '*' && operatorChar != '/') { return false; } //除法的時候除數不能為0 if(operatorChar == '/' && calStack.top() == 0) { return false; } return true; } int getOperatorRslt(int firstNum,int secondNum,char operatorChar) { switch(operatorChar) { case '+': return firstNum + secondNum; case '-': return firstNum - secondNum; case '*': return firstNum * secondNum; case '/': return firstNum / secondNum; default: cout<<"getOperatorRslt,inputPara wrong,firstNum = "<<firstNum<<",secondNum = "<<secondNum <<",operatorChar = "<<operatorChar<<endl; return 0; } } int evalRPN(vector<string>& tokens) { //后綴表達式的計算，用棧 size_t length = tokens.size(); if(length == 0) { return 0; } if(length == 1) { return stoi(tokens[0]); } stack<int> calStack; int tempNum; int firstNum; int secondNum; char operatorChar; for(size_t i = 0;i < length;i++) { //也可以用C++11的stoi tempNum = atoi(tokens[i].c_str()); //字符串是0進棧,0的場景前提不包括多個0 if(tokens[i].size() == 1 && tokens[i].at(0) == '0') { calStack.push(0); continue; } //是數字就進棧 if(tempNum != 0) { calStack.push(tempNum); continue; } //是+，-，*，/且滿足當前棧要求 if(isOperatorAndLegal(calStack,tokens[i])) { operatorChar = tokens[i].at(0); secondNum = calStack.top(); calStack.pop(); firstNum = calStack.top(); calStack.pop(); calStack.push(getOperatorRslt(firstNum,secondNum,operatorChar)); } else { return 0; } } //最后要判斷當前棧是否只有一個元素 if(calStack.size() == 1) { return calStack.top(); } else { return 0; } }};
