EEPW论坛

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

题意：逆波兰应用，很明显要考察的是栈；要注意的是，就是新来的符号，将栈中两个值取出进行操作。再放回栈中。

此时先取出的num2,后取出的是num1;进行num1和num2的操作；

1. class Solution  

2. {  

3. public:  

4.     int evalRPN(vector<string> &tokens)  

5.     {  

6.         if (tokens.empty())  

7.         {  

8.             return 0;  

9.         }  

10.   

11.         stack<int> st;  

12.   

13.         for (int i=0; i<tokens.size(); i++)  

14.         {  

15.             string s = tokens[i];  

16.             if (s =="+" || s=="-"  

17.                 || s=="*" || s=="/")  

18.             {  

19.                 if (st.size()<2)  

20.                 {  

21.                     return 0;  

22.                 }  

23.                 int num2 = st.top();  

24.                 st.pop();  

25.   

26.                 int num1 = st.top();  

27.                 st.pop();  

28.                 int result = 0;  

29.   

30.                 if (s=="+")  

31.                 {  

32.                     result = num1 + num2;  

33.                 }  

34.                 if (s == "-")  

35.                 {  

36.                     result = num1 - num2;  

37.                 }  

38.                 if (s == "*")  

39.                 {  

40.                     result = num1 * num2;  

41.                 }  

42.                 if (s == "/")  

43.                 {  

44.                     result = num1 / num2;  

45.                 }  

46.   

47.                 st.push(result);  

48.             }  

49.             else  

50.             {  

51.                 st.push(atoi(s.c_str()));  

52.             }  

53.         }  

54. return st.top();  

55.   

56.     }  

57. };