題目：求4+4/2-9*3的值；

思路：

　?、?#xff1a;用一個(gè)字符型數(shù)組存放了表達(dá)式《4+4/2-9*3》；

1 char val[9] = {'4','+','4','/','2','-','9','*','3'};

　?、?#xff1a;定義兩個(gè)棧，一個(gè)存放數(shù)字，一個(gè)存放符號(hào)；

1 //定義存儲(chǔ)整型的棧 2 typedef struct node 3 { 4 int data[MAXSIZE]; 5 int top; 6 }SeqStack; 7 //定義存儲(chǔ)字符型的棧 8 typedef struct nodeb 9 { 10 char data[MAXSIZE]; 11 int top; 12 }SeqStackchar;

　　③：定義符號(hào)的優(yōu)先級(jí)；

1 //獲取優(yōu)先級(jí) 2 int youxianquan(char c) 3 { 4 int x; 5 switch(c) 6 { 7 case '-': 8 case '+': 9 x = 1; 10 break; 11 case '*': 12 case '/': 13 x = 2; 14 break; 15 default: printf("error"); 16 } 17 return(x); 18 }

　?、?#xff1a;確定運(yùn)算思路——自左掃描表達(dá)式的每一個(gè)字符時(shí)，若當(dāng)前字符是運(yùn)算數(shù)值，入整型棧。是運(yùn)算符時(shí)，若這個(gè)運(yùn)算符比棧頂運(yùn)算符高則入棧，繼續(xù)向后處理，若這個(gè)運(yùn)算符比棧頂運(yùn)算符低，則從對(duì)象棧出棧兩個(gè)運(yùn)算量，從運(yùn)算符棧出棧一個(gè)運(yùn)算符進(jìn)行運(yùn)算，將其運(yùn)算結(jié)果入對(duì)象棧。然后繼續(xù)判斷當(dāng)前字符串是否高于棧頂運(yùn)算符，如果比棧頂運(yùn)算符高，則入棧，否則則繼續(xù)運(yùn)算。

1 //表達(dá)式求值 2 int result(SeqStack *a, SeqStackchar *b) 3 { 4 char val[9] = {'4','+','4','/','2','-','9','*','3'}; //創(chuàng)建表達(dá)式 5 int i,resultval; 6 int x,y; 7 char c; 8 int n = sizeof(val); 9 for(i = 0; i < n; i++) 10 { 11 c = val[i]; //獲取表達(dá)式第i個(gè)值 12 if(i%2 == 0) //把數(shù)字和符號(hào)區(qū)分開(kāi)來(lái)， 13 { 14 a->top++; 15 a->data[a->top] = c - '0'; //存放數(shù)值的 16 } 17 else //存放符號(hào)的 18 { 19 if(b->top == -1) //如果b為空則直接存入符號(hào) 20 { 21 b->top++; 22 b->data[b->top] = c; 23 } 24 else 25 { 26 x = youxianquan(c); //求出當(dāng)前符號(hào)的優(yōu)先級(jí) 27 y = youxianquan(b->data[b->top]); //求b棧頂?shù)姆?hào)優(yōu)先級(jí) 28 if(x > y) //如果當(dāng)前優(yōu)先級(jí)大于棧頂優(yōu)先級(jí)，則進(jìn)棧 29 { 30 b->top++; 31 b->data[b->top] = c; 32 } 33 else 34 { 35 resultval = abyunsuan(a,b); //否則a的前兩個(gè)出棧，b的棧頂出棧，然后進(jìn)行運(yùn)算，運(yùn)算結(jié)果再進(jìn)棧a； 36 y = youxianquan(b->data[b->top]); //繼續(xù)判斷表達(dá)式第i個(gè)值的優(yōu)先級(jí)是否大于棧頂符號(hào)的優(yōu)先級(jí) 37 if(x > y) //如果當(dāng)前優(yōu)先級(jí)大于棧頂優(yōu)先級(jí)，則進(jìn)棧 38 { 39 b->top++; 40 b->data[b->top] = c; 41 } 42 else //否則重復(fù)上面的操作對(duì)a的前兩個(gè)出棧值和b的棧頂出棧并且運(yùn)算 43 { 44 resultval = abyunsuan(a,b); 45 //由于每次循環(huán)都會(huì)對(duì)b的棧頂符號(hào)的優(yōu)先級(jí)做對(duì)比，所以?xún)?yōu)先級(jí)的對(duì)比只做一次即可 46 b->top++; //把當(dāng)前的符號(hào)進(jìn)b棧 47 b->data[b->top] = c; 48 } 49 } 50 } 51 } 52 while(i == n - 1 && a->top != -1 && b->top != -1) //當(dāng)運(yùn)算符輸入完時(shí) 53 { 54 resultval = abyunsuan(a,b); 55 } 56 } 57 return resultval; 58 } 1 //a出棧兩個(gè)值 b出棧棧頂運(yùn)算符，進(jìn)行運(yùn)算 2 int abyunsuan(SeqStack *a, SeqStackchar *b) 3 { 4 int fir,sec,resultval; 5 char topchar; 6 fir = a->data[a->top]; 7 a->top--; 8 sec = a->data[a->top]; 9 a->top--; 10 topchar = b->data[b->top]; //b的棧頂出棧 11 b->top--; 12 resultval = yunsuan(sec,fir,topchar); 13 a->top++; 14 a->data[a->top] = resultval; 15 return(resultval); 16 }

全部代碼如下：

1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 5 #define MAXSIZE 1024 6 7 //定義存儲(chǔ)整型的棧 8 typedef struct node 9 { 10 int data[MAXSIZE]; 11 int top; 12 }SeqStack; 13 //定義存儲(chǔ)字符型的棧 14 typedef struct nodeb 15 { 16 char data[MAXSIZE]; 17 int top; 18 }SeqStackchar; 19 20 //創(chuàng)建整型棧 21 SeqStack *creat_sa() 22 { 23 SeqStack *s; 24 s = (SeqStack *)malloc(sizeof(SeqStack)); 25 s->top = -1; 26 return(s); 27 } 28 //創(chuàng)建字符串棧 29 SeqStackchar *creat_sb() 30 { 31 SeqStackchar *s; 32 s = (SeqStackchar *)malloc(sizeof(SeqStackchar)); 33 s->top = -1; 34 return(s); 35 } 36 37 //函數(shù)聲明 38 int youxianquan(char c); 39 int yunsuan(int a, int b, char c); 40 int result(SeqStack *a, SeqStackchar *b); 41 int abyunsuan(SeqStack *a, SeqStackchar *b); 42 43 //獲取優(yōu)先級(jí) 44 int youxianquan(char c) 45 { 46 int x; 47 switch(c) 48 { 49 case '-': 50 case '+': 51 x = 1; 52 break; 53 case '*': 54 case '/': 55 x = 2; 56 break; 57 default: printf("error"); 58 } 59 return(x); 60 } 61 62 //開(kāi)始運(yùn)算 63 int yunsuan(int a, int b, char c) 64 { 65 int result; 66 switch(c) 67 { 68 case '*': 69 result = a * b; 70 break; 71 case '/': 72 result = a / b; 73 break; 74 case '+': 75 result = a + b; 76 break; 77 case '-': 78 result = a - b; 79 break; 80 } 81 return(result); 82 } 83 84 //a出棧兩個(gè)值 b出棧棧頂運(yùn)算符，進(jìn)行運(yùn)算 85 int abyunsuan(SeqStack *a, SeqStackchar *b) 86 { 87 int fir,sec,resultval; 88 char topchar; 89 fir = a->data[a->top]; 90 a->top--; 91 sec = a->data[a->top]; 92 a->top--; 93 topchar = b->data[b->top]; //b的棧頂出棧 94 b->top--; 95 resultval = yunsuan(sec,fir,topchar); 96 a->top++; 97 a->data[a->top] = resultval; 98 return(resultval); 99 } 100 101 //表達(dá)式求值 102 int result(SeqStack *a, SeqStackchar *b) 103 { 104 char val[9] = {'4','+','4','/','2','-','9','*','3'}; //創(chuàng)建表達(dá)式 105 int i,resultval; 106 int x,y; 107 char c; 108 int n = sizeof(val); 109 for(i = 0; i < n; i++) 110 { 111 c = val[i]; //獲取表達(dá)式第i個(gè)值 112 if(i%2 == 0) //把數(shù)字和符號(hào)區(qū)分開(kāi)來(lái)， 113 { 114 a->top++; 115 a->data[a->top] = c - '0'; //存放數(shù)值的 116 } 117 else //存放符號(hào)的 118 { 119 if(b->top == -1) //如果b為空則直接存入符號(hào) 120 { 121 b->top++; 122 b->data[b->top] = c; 123 } 124 else 125 { 126 x = youxianquan(c); //求出當(dāng)前符號(hào)的優(yōu)先級(jí) 127 y = youxianquan(b->data[b->top]); //求b棧頂?shù)姆?hào)優(yōu)先級(jí) 128 if(x > y) //如果當(dāng)前優(yōu)先級(jí)大于棧頂優(yōu)先級(jí)，則進(jìn)棧 129 { 130 b->top++; 131 b->data[b->top] = c; 132 } 133 else 134 { 135 resultval = abyunsuan(a,b); //否則a的前兩個(gè)出棧，b的棧頂出棧，然后進(jìn)行運(yùn)算，運(yùn)算結(jié)果再進(jìn)棧a； 136 b->top++; 137 b->data[b->top] = c; 138 } 139 } 140 } 141 while(i == n - 1 && a->top != -1 && b->top != -1) //當(dāng)運(yùn)算符輸入完時(shí) 即當(dāng)所有的字符全部輸入完時(shí)才執(zhí)行此循環(huán) 142 { 143 resultval = abyunsuan(a,b); 144 } 145 }

　　　　　//也可以把上面的一個(gè)while循環(huán)注釋掉，然后加上下面的循環(huán)；
　　　　/*
　　　　　　while(a=>top != -1 && b->top != -1)
　　　　　　　　resultval = abyunsuan(a,b);
　　　　*/
146 return resultval; 147 } 148 149 void main() 150 { 151 SeqStack *a; 152 SeqStackchar *b; 153 int resultval; 154 a = creat_sa(); //創(chuàng)建鏈表a 155 b = creat_sb(); //創(chuàng)建鏈表b 156 resultval = result(a,b); 157 printf("%d",resultval); 158 159 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ngnetboy/archive/2012/09/28/2706457.html

總結(jié)

以上是生活随笔為你收集整理的【数据结构】用栈解决表达式求值问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。