逆波兰表达式：

计算给定的逆波兰表达式的值，有效操作只有加减乘除，每个操作数都为整数。

如：

"2"，"1"，"+"，"3"，"*" ： 9；---------（2+1）*3

"4"，"13"，"5"，"/"，"+" ： 6；---------4+（13/5）

程序实现：

 1 #include <iostream>
 2 #include <stack>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 //判断是否为运算符
 7 bool IsOperator(const char* token){
 8     return ((token[0]=='+')||(token[0]=='-')
 9     ||(token[0]=='*')||(token[0]=='/'));
10 }
11 //逆波兰表达式，利用压栈出栈的方式：
12 /*
13 若当前字符为操作数，则压栈
14 若当前字符为操作符，则弹出栈中的两个操作数，进行计算后再次压入栈中
15 */
16 int ReversePolishNotation(const char* str[],int size){
17     stack<int> s;
18     int a,b;
19     const char* token;
20     for(int i=0;i<size;i++){
21         token = str[i];
22         if(!IsOperator(token))
23             s.push(atoi(token));
24         else{
25             b = s.top();
26             s.pop();
27             a = s.top();
28             s.pop();
29             if(token[0] == '+')
30                 s.push(a+b);
31             else if(token[0] == '-')
32                 s.push(a-b);
33             else if(token[0] == '*')
34                 s.push(a*b);
35             else if(token[0] == '/')
36                 s.push(a/b);
37         }
38     }
39     return s.top();
40 }
41 int main()
42 {
43     const char* str[] = {"2","1","+","3","*"};
44     const char* str1[] = {"4","13","5","/","+"};
45     int value = ReversePolishNotation(str,sizeof(str)/sizeof(const char*));
46     cout<<value<<endl;
47     cout<<ReversePolishNotation(str1,sizeof(str1)/sizeof(const char*))<<endl;
48     return 0;
49 }

运行结果：

转载请注明出处：

C++博客园：godfrey_88

http://www.cnblogs.com/gaobaoru-articles/