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