首页 > 代码库 > Evaluate Reverse Polish Notation
Evaluate Reverse Polish Notation
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
思路：根据逆波兰表示法的特点，可以使用栈来求解本题，依次遍历输入tokens的每一个元素，
若当前元素为数字，则将其入栈；否则，当前元素表示运算操作，弹出栈顶元素和次栈顶元素，即可获得该运算的左右操作数，将运算结果入栈；重复上述操作。
返回栈顶元素。
1 int evalRPN( vector<string> &tokens ) { 2 if( tokens.empty() ) { return 0; } 3 stack<int> numStack; 4 for( size_t i = 0; i != tokens.size(); ++i ) { 5 if( tokens[i] == "+" ) { 6 int tmp = numStack.top(); numStack.pop(); 7 numStack.top() += tmp; 8 } else if( tokens[i] == "-" ) { 9 int tmp = numStack.top(); numStack.pop();10 numStack.top() -= tmp;11 } else if( tokens[i] == "*" ) {12 int tmp = numStack.top(); numStack.pop();13 numStack.top() *= tmp;14 } else if( tokens[i] == "/" ) {15 int tmp = numStack.top(); numStack.pop();16 assert( tmp != 0 );17 numStack.top() /= tmp;18 } else {19 numStack.push( atoi( tokens[i].c_str() ) );20 }21 }22 return numStack.top();23 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。