剛才發表了一篇后綴表達式求值（逆波蘭表達式求值）的代碼，雖然其在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セ 閱讀(6066)
評論(5) 編輯 收藏 引用 所屬分類:
C++