1、需求分析
設計一個程序，演示用算符優先法對算術表達式求值的過程。利用算符優先關系，實現對算術四則混合運算表達式的求值。
（1）輸入的形式：表達式，例如2*(3+4)
???? 包含的運算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')'；
（2）輸出的形式：運算結果，例如2*(3+4)=14；
（3）程序所能達到的功能：對表達式求值并輸出
2、系統設計
1、棧的抽象數據類型定義：
ADT Stack{
數據對象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
數據關系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}
????????? 約定an端為棧頂，ai端為棧底
基本操作：
Push(&S,e)
初始條件：棧S已存在
操作結果：插入元素e為新的棧頂元素
Pop(&S,&e)
初始條件：棧S已存在且非空
操作結果：刪除S的棧頂元素，并用e返回其值
}ADT Stack
3、各個模塊的主要功能：
*Push(SC *s,char c)：把字符壓棧
*Push(SF *s,float f)：把數值壓棧
*Pop(SC *s)：把字符退棧
*Pop(SF *s)：把數值退棧
Operate(a,theta,b)：根據theta對a和b進行'+' 、'-' 、'*' 、'/' 、'^'操作
In(Test,*TestOp)：若Test為運算符則返回true，否則返回false
ReturnOpOrd(op,*TestOp)：若Test為運算符，則返回此運算符在數組中的下標
precede(Aop,Bop)：根據運算符優先級表返回Aop與Bop之間的優先級
EvaluateExpression(*MyExpression)：用算符優先法對算術表達式求值
完整的程序代碼如下：
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"math.h"
#define true 1
#define false 0
#define OPSETSIZE 8
typedef int Status; unsigned char Prior[8][8] =
{ // 運算符優先級表 // '+' '-' '*' '/' '(' ')' '#' '^' /*'+'*/'>','>','<','<','<','>','>','<', /*'-'*/'>','>','<','<','<','>','>','<', /*'*'*/'>','>','>','>','<','>','>','<', /*'/'*/'>','>','>','>','<','>','>','<', /*'('*/'<','<','<','<','<','=',' ','<', /*')'*/'>','>','>','>',' ','>','>','>', /*'#'*/'<','<','<','<','<',' ','=','<', /*'^'*/'>','>','>','>','<','>','>','>'
}; typedef struct StackChar
{char c; struct StackChar *next;
}SC; //StackChar類型的結點SCtypedef struct StackFloat
{float f; struct StackFloat *next;
}SF; //StackFloat類型的結點SFSC *Push(SC *s,char c) //SC類型的指針Push，返回p
{SC *p=(SC*)malloc(sizeof(SC)); p->c=c; p->next=s; return p;
} SF *Push(SF *s,float f) //SF類型的指針Push，返回p
{SF *p=(SF*)malloc(sizeof(SF)); p->f=f; p->next=s; return p;
} SC *Pop(SC *s) //SC類型的指針Pop
{SC *q=s; s=s->next; free(q); return s;
} SF *Pop(SF *s) //SF類型的指針Pop
{SF *q=s; s=s->next; free(q); return s;
} float Operate(float a,unsigned char theta, float b) //計算函數Operate
{switch(theta){case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; case '^': return pow(a,b); default : return 0; }
} char OPSET[OPSETSIZE]={'+','-','*','/','(',')','#','^'}; Status In(char Test,char *TestOp)
{int Find=false; for (int i=0; i< OPSETSIZE; i++){if(Test == TestOp[i])Find= true; } return Find;
} Status ReturnOpOrd(char op,char *TestOp)
{ for(int i=0; i< OPSETSIZE; i++){if (op == TestOp[i])return i;}
}char precede(char Aop, char Bop)
{ return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)];
} float EvaluateExpression(char* MyExpression)
{ // 算術表達式求值的算符優先算法// 設OPTR和OPND分別為運算符棧和運算數棧，OP為運算符集合 SC *OPTR=NULL; // 運算符棧，字符元素 SF *OPND=NULL; // 運算數棧，實數元素 char TempData[20]; float Data,a,b; char theta,*c,Dr[]={'#','\0'}; OPTR=Push(OPTR,'#'); c=strcat(MyExpression,Dr); strcpy(TempData,"\0");//字符串拷貝函數 while (*c!= '#' || OPTR->c!='#'){ if (!In(*c, OPSET)){ Dr[0]=*c; strcat(TempData,Dr); //字符串連接函數 c++; if (In(*c, OPSET)){ Data=atof(TempData); //字符串轉換函數(double) OPND=Push(OPND, Data); strcpy(TempData,"\0"); } } else // 不是運算符則進棧 {switch (precede(OPTR->c, *c)){case '<': // 棧頂元素優先級低 OPTR=Push(OPTR, *c); c++; break; case '=': // 脫括號并接收下一字符 OPTR=Pop(OPTR); c++; break; case '>': // 退棧并將運算結果入棧 theta=OPTR->c;OPTR=Pop(OPTR); b=OPND->f;OPND=Pop(OPND); a=OPND->f;OPND=Pop(OPND); OPND=Push(OPND, Operate(a, theta, b)); break; } //switch} } //while return OPND->f;
} //EvaluateExpression int main(void)
{ char s[128];puts("請輸入表達式:"); gets(s);puts("該表達式的值為:"); printf("%s\b=%g\n",s,EvaluateExpression(s));system("pause");return 0;
}
???? 測試結果如下：
?
總結
以上是生活随笔為你收集整理的数据结构课程设计---------用栈来实现表达式求值的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
