首页 > 代码库 > LeetCode:Evaluate Reverse Polish Notation
LeetCode: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解题思路: 由于题目给出的已经是一个求值表达式的后缀式(又称“波兰式”),所以不用我们自己再将求值表达式转换为后缀式。既然已知后缀式,那求取表达式的值就比较简单了。 步骤: 1.如果当前是操作符,从栈中取出栈顶的两个元素,将其表达式的值入栈. 2.如果当前是数字,直接将其入栈. 3.不断重复上述过程,直到遍历完整个后缀式,最后,栈顶就是所要求的值.下面是解题代码:class Solution { public: int evalRPN(vector<string> &tokens) { stack<int> stk; for(unsigned i=0,len=tokens.size();i<len;++i) { if(tokens[i].size() == 1 && ( tokens[i][0] < ‘0‘ || tokens[i][0] > ‘9‘)) { char opt = tokens[i][0] ; int a , b ; b = stk.top() , stk.pop(); a = stk.top() , stk.pop(); if(opt == ‘+‘ || opt == ‘-‘) stk.push(opt == ‘+‘ ? a + b : a - b ); else stk.push(opt == ‘*‘ ? a * b : a / b ); continue; } bool flag = tokens[i][0] == ‘-‘ ; unsigned j = tokens[i][0] == ‘+‘ || tokens[i][0] == ‘-‘ , len1 = tokens[i].size(); int num = 0 ; for(;j<len1;++j) num = num * 10 + tokens[i][j] - ‘0‘ ; num *= flag ? -1 : 1 ; stk.push(num); } return stk.top(); } };
注:上述程序是我经过测试后台数据没有类似["-","-9"]这种后缀式的缩写代码,如果后台
存在这种数据,需要另加判断,不过,本质上都是一样的.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。