[leetcode] 150. Evaluate Reverse Polish Notation

[leetcode] 150. Evaluate Reverse Polish Notation

Description

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

Division between two integers should truncate toward zero.The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.Example 1:

Input: ["2", "1", "+", "3", "*"]Output: 9Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]Output: 6Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]Output: 22Explanation: ((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]<='9')||(token[0]=='-'&&token.size()>1)){ int num=0; int i=0; int flag=1; if(token[i]=='-'){ flag=-1; i++; } while(token[i]!='\0'){ num=num*10+token[i]-'0'; i++; } s.push(flag*num); }else if(token[0]=='+'||token[0]=='-'||token[0]=='*'||token[0]=='/'){ int a=s-(); s.pop(); int b=s-(); 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-(); }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。