剛才發(fā)表了一篇后綴表達(dá)式求值（逆波蘭表達(dá)式求值）的代碼，雖然其在visual C++2010中編譯出現(xiàn)了問題，不過幸好有好心人的熱心幫助解決了。
那么為什么要用后綴表達(dá)式求值?根據(jù)我自己的理解，后綴表達(dá)式求值不必判斷運(yùn)算符的優(yōu)先級(jí)，只要按順序執(zhí)行。每遇到一個(gè)操作符就處理一次，便于計(jì)算機(jī)處理。
那么下面我就分享一下我的中綴表達(dá)式轉(zhuǎn)后綴的代碼：
也許大家在考試時(shí)轉(zhuǎn)化一定會(huì)：
中綴表達(dá)式：（8+9*10）-4/2+3
其轉(zhuǎn)化思路：
1、將每個(gè)操作符對(duì)應(yīng)的兩個(gè)操作數(shù)用括號(hào)括上（（（8+（9*10））-（4/2））+3）
2、將操作符移到對(duì)應(yīng)的括號(hào)外（（（8（910*）+）（42）/）-3）+
3、去掉括號(hào)即可 8910*+42/-3+
如果要用數(shù)據(jù)結(jié)構(gòu)中的棧和隊(duì)列實(shí)現(xiàn)
1、用一個(gè)字符串存儲(chǔ)表達(dá)式
2、掃描字符串。當(dāng)其為0--9時(shí)直接入隊(duì)列，遇到左括號(hào)入棧，操作符級(jí)別 #：0用于最后判斷，+ -：1,* /:2
3、首先向堆中放一個(gè)#，當(dāng)進(jìn)入堆的操作符的級(jí)別不小于棧頂操作符的優(yōu)先級(jí)，則入棧，否則彈出棧頂元素并進(jìn)入隊(duì)列，將下一個(gè)操作符壓入棧。
4、一直循環(huán)直到將所有字符處理完
5、最后將所有元素出隊(duì)列并打印就可得到后綴表達(dá)式
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//自定義隊(duì)列
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//定義運(yùn)算符的優(yōu)先級(jí)
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){//中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式(自己的實(shí)驗(yà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("請(qǐng)輸入中綴表達(dá)式:");
129 gets(str);
130 printf("后綴表達(dá)式:");
131 Middle_Bhind(st,Mq,str,Max);
132}
133
134
135
136
137
posted on 2011-01-19 15:51
あ維wêiセ 閱讀(6037)
評(píng)論(5) 編輯 收藏 引用 所屬分類:
C++