表示式求值--資料結構課本演算法實現

資料結構演算法 · 發表 2018-10-21 13:28:00

摘要：這篇部落格介紹的表示式求值是用 C語言實現的，只使用了c++裡面的引用。資料結構課本上的一個例題，但是看起來很簡單，實現卻遇到了很多問題。這個題需要構建兩個棧，一個用來儲存運算子OPTR，一個用來儲存數字OPND。但是，數字和運算子都定...

這篇部落格介紹的表示式求值是用 C語言 實現的，只使用了c++裡面的引用。

資料結構課本上的一個例題，但是看起來很簡單，實現卻遇到了很多問題。

這個題需要構建兩個棧，一個用來儲存運算子OPTR，一個用來儲存數字OPND。

但是，數字和運算子都定義成字元型棧嗎？

出現了問題，當運算結果或中間結果為負時，沒有辦法儲存。而且只能運算0~9之間的數字結果也只能是0~9之間。

那就運算子棧為字元棧，數字棧為數值型棧，在儲存時將表示式中的字元轉化成數值進行儲存。

但是，如果我們不用c++裡面的stack進行棧的定義，而是用C語言進行實現，這種方法實現起來好像也沒有這麼簡單，程式碼很多。兩種棧的元素型別不一樣，操作很繁瑣。

怎麼辦呢，我想可以用char型別的ASCII碼數值來表示數值，兩個棧都定義為字元棧。

數值進行儲存時，將讀入的字元型變數值減去0的ASCII碼值 c - '0' ，然後壓棧。

但這樣做也有缺陷，應為C語言中char型別只有8位，那這種方法實現的表示式求值，其結果和中間值的取值範圍[ -127, 128] 。

我們主要是學習棧的實現和應用，其實對於這個題來說已經足夠了。

下面附上程式碼的實現：

1 #include <stdio.h>
2 #include <stdlib.h>
3 
4 
5 #define ElemType char
6 #define STACKINCEMENT 10
7 #define STACK_INIT_SIZE 50
8 
9 #define Status int
 10 #define OK 1
 11 #define ERROR 0
 12 #define OVERFLOW -2
 13 
 14 typedef struct{
 15ElemType *base;
 16ElemType *top;
 17int stacksize;
 18 }SqStack;
 19 
 20 Status InitStack(SqStack &S){
 21S.top = S.base = (ElemType *)malloc(sizeof(ElemType) * STACK_INIT_SIZE);
 22if(!S.top)
 23exit(OVERFLOW);
 24S.stacksize = STACK_INIT_SIZE;
 25return OK;
 26 }//InitStack
 27 
 28 Status Push(SqStack &S, ElemType e){
 29if(S.top - S.base == S.stacksize){
 30S.base = (ElemType *)realloc(S.base, sizeof(ElemType) *
 31(S.stacksize + STACKINCEMENT));
 32if(!S.base) exit(OVERFLOW);
 33S.top = S.base + S.stacksize;
 34S.stacksize += STACKINCEMENT;
 35}
 36*S.top++ = e;
 37return OK;
 38 }//Push
 39 
 40 Status Pop(SqStack &S, ElemType &e){
 41if(S.base == S.top) return ERROR;
 42 
 43e = *--S.top;
 44return OK;
 45 }//Pop
 46 
 47 ElemType GetTop(SqStack S){
 48if(S.base == S.top) return ERROR;
 49return *--S.top;
 50 }//GetTop
 51 
 52 Status In(ElemType c){
 53if(c=='+'||c=='-'||c=='*'||c=='/'||c=='#'||c=='('||c==')'||c=='['||c==']')
 54return 1;
 55else
 56return 0;
 57 }//In
 58 
 59 char Precede(ElemType a, ElemType b){
 60if(a=='+'||a=='-'){
 61if(b=='+'||b=='-'||b=='>'||b=='#'||b==')'||b==']')
 62return '>';
 63else return '<';
 64}
 65if(a=='*'||a=='/'){
 66if(b=='('||b=='[')
 67return '<';
 68else return '>';
 69}
 70if(a=='('){
 71if(b==')')
 72return '=';
 73else return '<';
 74}
 75if(a=='['){
 76if(b==']')
 77return '=';
 78else return '<';
 79}
 80if(a=='#'){
 81if(b=='#')
 82return '=';
 83else return '<';
 84}
 85 }//Precede
 86 
 87 ElemType Operate(ElemType a, ElemType x, ElemType b){
 88switch (x){
 89case '+':
 90return a+ b;
 91case '-':
 92return a- b;
 93case '*':
 94return a * b;
 95case '/':
 96return a / b;
 97}
 98 }//Operator
 99 
100 ElemType EvaluateExpression(){
101SqStack OPTR, OPND;
102InitStack(OPTR); //操作符
103Push(OPTR, '#');
104InitStack(OPND); //運算元
105 
106char x, c[100];
107gets(c);
108int i=0;
109while(c[i] != '#' || GetTop(OPTR)!='#'){
110if(!In(c[i])) {
111if(i>0 && (c[i-1]>'0'&& c[i-1]<='9')){
112Pop(OPND, x);
113Push(OPND, 10*x + c[i] - '0');
114}
115else Push(OPND, c[i] - '0');
116i++;
117}
118else
119switch(Precede(GetTop(OPTR), c[i])){
120case '<':
121Push(OPTR, c[i]);
122i++;
123break;
124case '=':
125Pop(OPTR, x);
126i++;
127break;
128case '>':
129Pop(OPTR, x);
130ElemType a, b;
131Pop(OPND, b); Pop(OPND, a);
132Push(OPND, Operate(a, x, b));
133break;
134}
135}
136return GetTop(OPND);
137 }//EvaluateExpression
138 
139 int main(){
140SqStack S;
141InitStack(S);
142printf("%d",EvaluateExpression());
143 
144return 0;
145 }

表示式求值--資料結構課本演算法實現

您可能也會喜歡…