刚才发表了一篇后缀表达式求值（逆波兰表达式求值）的代码，虽然其在visual C++2010中编译出现了问题，不过幸好有好心人的热心帮助解决了。
那么为什么要用后缀表达式求值?根据我自己的理解，后缀表达式求值不必判断运算符的优先级，只要按顺序执行。每遇到一个操作符就处理一次，便于计算机处理。
那么下面我就分享一下我的中缀表达式转后缀的代码：
也许大家在考试时转化一定会：
中缀表达式：（8+9*10）-4/2+3
其转化思路：
1、将每个操作符对应的两个操作数用括号括上（（（8+（9*10））-（4/2））+3）
2、将操作符移到对应的括号外（（（8（910*）+）（42）/）-3）+
3、去掉括号即可 8910*+42/-3+
如果要用数据结构中的栈和队列实现
1、用一个字符串存储表达式
2、扫描字符串。当其为0--9时直接入队列，遇到左括号入栈，操作符级别 #：0用于最后判断，+ -：1,* /:2
3、首先向堆中放一个#，当进入堆的操作符的级别不小于栈顶操作符的优先级，则入栈，否则弹出栈顶元素并进入队列，将下一个操作符压入栈。
4、一直循环直到将所有字符处理完
5、最后将所有元素出队列并打印就可得到后缀表达式
1
#include<stdio.h>
2#define Max 20
3//自定义栈
4template<class Elem>
5
struct Stack
{
6
int top;
7 Elem *p;
8 int size;
9
};
10template<class Elem>
11void Set_Ssize(Stack<Elem> &sta,int n){
12 sta.size=n;
13 sta.p=new Elem[sta.size];
14 sta.top=0;
15}
16template<class Elem>
17void Push(Stack<Elem> &sta,Elem item){
18 sta.p[sta.top++]=item;
19}
20template<class Elem>
21void Pop(Stack<Elem> &sta,Elem &e){
22 e=sta.p[--sta.top];
23}
24template<class Elem>
25bool IsEmpty(Stack<Elem> &sta){
26 return sta.top==0;
27}
28template<class Elem>
29bool IsFull(Stack<Elem> &sta){
30 return sta.top==sta.size;
31}
32//自定义队列
33template<class Elem>
34struct MyQuene{
35 int front;
36 int rear;
37 Elem *p;
38 int size;
39};
40template<class Elem>
41void Set_Qsize(MyQuene<Elem> &Q,int n){
42 Q.size=n;
43 Q.front=0;
44 Q.rear=0;
45 Q.p=new Elem[Q.size];
46}
47template<class Elem>
48void AddQuene(MyQuene<Elem> &Q,Elem item){
49 Q.p[Q.rear++]=item;
50 if(Q.rear==Q.size)
51 Q.rear=0;
52}
53template<class Elem>
54void DeleteQuene(MyQuene<Elem> &Q,Elem& e){
55 e=Q.p[Q.front++];
56 if(Q.front==Q.size)
57 Q.front=0;
58}
59template<class Elem>
60Elem GetTop(Stack<Elem> &sta){
61 return sta.p[sta.top-1];
62}
63template<class Elem>
64bool IsEmpty(MyQuene<Elem> &Q){
65 return Q.front==Q.rear;
66}
67template<class Elem>
68bool IsFull(MyQuene<Elem> &Q){
69 int len=Q.front<Q.rear?Q.rear-Q.front:Q.rear-Q.front+Q.size;
70 return len==Q.size-1;
71}
72//定义运算符的优先级
73int GetPrecedence(char a){
74
switch(a){
75 case '#':return 0;
76 case '+':
77 case '-':return 1;
78 case '*':
79 case '/':return 2;
80 case '^':return 3;
81 default:break;
82
}
83}
84template<class Elem>
85void Middle_Bhind(Stack<Elem> &st,MyQuene<Elem>&Mq,char*A,int n){//中缀表达式转为后缀表达式(自己的实验需求)
86 Set_Ssize(st,n);
87 Set_Qsize(Mq,n+1);
88 char tem;
89 int i=0;
90 Push(st,'#');
91 do{
92 if((A[i]>='0'&&A[i]<='9')||(A[i]>='A'&&A[i]<='Z')||(A[i]>='a'&&A[i]<='z'))
93 AddQuene(Mq,A[i]);
94 else if(A[i]=='(')
95 Push(st,A[i]);
96 else if(A[i]==')'){
97 while(GetTop(st)!='('){
98 Pop(st,tem);
99 AddQuene(Mq,tem);
100 }
101 Pop(st,tem);
102 }
103 else if(GetTop(st)=='(')
104 Push(st,A[i]);
105 else{
106 while(GetPrecedence(A[i])<=GetPrecedence(GetTop(st))){
107 Pop(st,tem);
108 AddQuene(Mq,tem);
109 }
110 Push(st,A[i]);
111 }
112 i++;
113 }while(A[i]!='\0');
114 while(GetTop(st)!='#'){
115 Pop(st,tem);
116 AddQuene(Mq,tem);
117 }
118 while(!IsEmpty(Mq)){
119 DeleteQuene(Mq,tem);
120 printf("%c",tem);
121 }
122 putchar('\n');
123}
124void main(){
125 char str[Max];
126 Stack<char> st;
127 MyQuene<char>Mq;
128 printf("请输入中缀表达式:");
129 gets(str);
130 printf("后缀表达式:");
131 Middle_Bhind(st,Mq,str,Max);
132}
133
134
135
136
137
posted on 2011-01-19 15:51
あ维wêiセ 阅读(6015)
评论(5) 编辑 收藏 引用 所属分类:
C++