linux算术表达式求值数据结构,数据结构：算数表达式求值演示
題目：設計一個程序，演示用算符優先法對算數表達式求值的過程。
一、需求分析
以字符序列的形式從終端讀入輸入語法正確、不含變量的整數表達式。利用教科書表3.1給出的算符優先關系，實現對算數四則混合運算表達式的求值，并仿照教科書的例子3-1演示在求值中運算符棧、運算數棧、輸入字符和主要操作的變化過程。
2.測試數據
(1)3*(7-2);
(2)8;1+2+3+4;88-1*5;1024/4*8;1024/(4*8);(20+2)/(6/2);
(3)3-3-3;8/(9-9);2*(6+2*(3+6*(6+6)));(((6+6)*(6+3)*2+6)*2;
二、概要設計
1. 數據結構
主要數據類型為：
ADT Stack{
數據對象：
D={ai|a∈EleSet,i=1,2,...,n,n≥0}
數據關系：R1={|ai-1,ai∈D,i=2,...,n}
約定an為棧頂，a1為棧底。
基本操作：
InitStack(&S)
操作結果：構造一個空棧S
GetTop(S, &e)
初始條件：棧S已存在且非空
操作結果：用e返回S棧頂元素
Pop(&S, &e)
初始條件：棧S已存在
操作結果：刪除S的棧頂元素，并用e返回其值
Push(&S, e)
初始條件：棧S已存在
操作結果：插入e為新的棧頂元素
}
2. 使用函數
int InitTRStack(TRStack *S)
int InitNDStack(NDStack *S)
操作結果：構造運算符棧和操作數棧
char TRGetTop(TRStack *S)
float NDGetTop(NDStack *S)
操作結果：返回運算符棧和操作數棧的棧頂元素
int TRPush(TRStack *S, char e)
int NDPush(NDStack *S, float e)
操作結果：插入棧頂元素
int TRPop(TRStack *S, char *e)
int NDPop(NDStack *S, float *e)
操作結果：刪除棧頂元素，返回其值
float Opreate(float a, float b, char theta)
操作結果：對操作數和對應的運算符進行計算返回結果
int In(char c,char *OP)
操作結果：判定字符是否為運算符
char Precede(char m, char n, char *OP)
操作結果：判斷運算符的優先級
int OutPutNDStack(NDStack *S)
int OutPutTRStack(TRStack *S)
操作結果：輸出運算符和操作數棧內所有元素
三、詳細設計
1. 數據儲存結構
運算符棧采用char類型棧，操作數棧采用float類型棧
OPND和OPTR棧的實現如下：
typedef struct {
char *base;
char *top;
int stacksize;
}TRStack;
typedef struct {
float *base;
float *top;
int stacksize;
}NDStack;
2. 計算功能實現
為實現算符優先級算法，使用兩個工作棧，一個稱作OPTR，用以寄存運算符，一個稱作OPND，用以寄存操作爍或運算結果。算法的基本思想為：
(1)首先置操作數棧為空棧，表達式起始符“#”為運算符棧的棧底元素；
(2)依次讀入表達式中的每個字符，若是操作數則進OPND棧，若是運算符則和OPTR棧的棧頂運算符比較有限權后做相應操作，直到OPTR棧的棧頂元素和當前讀入字符均為“#”
float EvaluateExpression(char *expr){
// 算數表達式求值的算符優先算法。OPTR和OPND分別為運算符棧和運算數棧
// OP為運算數的集合
char OP[8] = {'+','-','*','/','(',')','#','\0'};
TRStack OPTR; NDStack OPND;
char *c;
char End[] = {'#','\0'};
char cc[254];
float a,b;
char theta,x;
float cf;
InitTRStack(&OPTR); TRPush(&OPTR,'#');
InitNDStack(&OPND); c = strcat(expr,End); // 拼接表達式使其以#結尾
while(*c!='#' || TRGetTop(&OPTR)!='#') {
if(!In(*c,OP)){
while(!In(*c,OP)){strcat(cc,c);c++;} // 兩位數以上數字輸入
cf = atof(cc);
OutPutTRStack(&OPTR);
OutPutNDStack(&OPND);
printf("輸入字符:%f ",cf);
memset(cc, 0x00, sizeof (char) * 256); // 清空臨時字符串
NDPush(&OPND,cf);
printf("操作:Push(OPND,%f)\n",cf);
} // 不是運算符進棧
else{
OutPutTRStack(&OPTR);
OutPutNDStack(&OPND);
printf("輸入字符:%c ",*c);
switch(Precede(TRGetTop(&OPTR),*c,OP)){
case'
TRPush(&OPTR,*c);
printf("操作:Push(OPTR,%c)\n",*c);
c++;
break;
case'=': // 脫括號指針移動到下一字符
TRPop(&OPTR,&x);
printf("操作:Pop(OPTR,%c)\n",x);
c++;
break;
case'>': // 退棧并將運算結果入棧
TRPop(&OPTR,&theta);
NDPop(&OPND,&b);
NDPop(&OPND,&a);
NDPush(&OPND,Opreate(a,b,theta));
printf("操作:Opreate(%f,%c,%f)\n",a,theta,b);
break;
}
}
}
OutPutTRStack(&OPTR);
OutPutNDStack(&OPND);
printf("輸入字符:%c ",*c);
printf("操作:return GetTop(OPND)\n");
return NDGetTop(&OPND);
}
4. 主程序
通過判斷讀入表達式中元素是否僅為數字和符號以及左右括號數目是否相等來決定是否進行下一步計算
int main(){
// cnt1,cnt2 記錄左右括號個數
// falg 標志輸入是否合法
char Exp[254];
int i = 0;
int cnt1 = 0;
int cnt2 = 0;
int flag = 0;
printf("input equation:\n");
gets(Exp);
char stdinput[17] = {'+','-','*','/','(',')','1','2','3','4','5','6','7','8','9','0','\0'};
while(Exp[i]!='\0'){
if(Exp[i]=='(') cnt1++;
if(Exp[i]==')') cnt2++;
if(!In(Exp[i],stdinput)) {flag = 1; break;}
else i++;
}
if(cnt1!=cnt2) flag = 1;
if(!flag) {printf("結果：%f",EvaluateExpression(Exp));}
else {printf("invalid input\n");}
}
5. 程序的層次結構
程序結構.png
五、用戶手冊
本程序的運行環境為DOS操作系統，執行文件為：calculation.exe
進入程序按提示操作，輸入表達式
輸入后按回車符即顯示結果
六、測試結果
(1) (((6+6)*6+3)*2+6)*2
測試結果.png
七、源代碼
calculation.c
#include
#include
#include
#include
#include
#define STACK_INIT_SIZE 1000
#define STACKNCREMENT 10
typedef struct {
char *base;
char *top;
int stacksize;
}TRStack;
typedef struct {
float *base;
float *top;
int stacksize;
}NDStack;
char TRGetTop(TRStack *S){
char e;
if(S->top == S->base) return 0;
e = *(S->top-1);
return e;
}
float NDGetTop(NDStack *S){
float e;
if(S->top == S->base) return 0;
e = *(S->top-1);
return e;
}
int InitTRStack(TRStack *S){
S->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
if(!S->base) exit(-2);
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
return 1;
}
int InitNDStack(NDStack *S){
S->base = (float *)malloc(STACK_INIT_SIZE * sizeof(float));
if(!S->base) exit(-2);
S->top = S->base;
S->stacksize = STACK_INIT_SIZE;
return 1;
}
int TRPush(TRStack *S, char e){
if(S->top - S->base >= S->stacksize){
S->base = (char *)realloc(S->base, (S->stacksize + STACK_INIT_SIZE * sizeof(char)));
if(!S->base) exit(-2);
S->top = S->base + S->stacksize;
S->stacksize += STACKNCREMENT;
}
*S->top++ = e;
return 1;
}
int NDPush(NDStack *S, float e){
if(S->top - S->base >= S->stacksize){
S->base = (float *)realloc(S->base, (S->stacksize + STACK_INIT_SIZE * sizeof(float)));
if(!S->base) exit(-2);
S->top = S->base + S->stacksize;
S->stacksize += STACKNCREMENT;
}
*S->top++ = e;
return 1;
}
int TRPop(TRStack *S, char *e){
if(S->top == S->base) return 0;
*e = * --S->top;
return 1;
}
int NDPop(NDStack *S, float *e){
if(S->top == S->base) return 0;
*e = * --S->top;
return 1;
}
float Opreate(float a, float b, char theta){
switch(theta){
case'+':return a+b;
case'-':return a-b;
case'/':return a/b;
case'*':return a*b;
default:return 0;
}
}
int In(char c,char *OP){
int flag = 0;
int i = 0;
while(OP[i]!='\0'){
if(OP[i]==c) flag=1;
i++;
}
return flag;
}
char Precede(char m, char n, char *OP){
unsigned char Prior[7][7] =
{'>','>','','>',
'>','>','','>',
'>','>','>','>','','>',
'>','>','>','>','','>',
'
'>','>','>','>',' ','>','>',
'
int i = 0; int j = 0;
while(m != OP[i]) i++;
while(n != OP[j]) j++;
return Prior[i][j];
}
int OutPutNDStack(NDStack *S){
float *c;
c = S->top;
printf("OPND棧: ");
while(c!=S->base){
c--;
printf("%f ",*c);
}
}
int OutPutTRStack(TRStack *S){
char *c;
c = S->top;
printf("OPTR棧: ");
while(c!=S->base){
c--;
printf("%c ",*c);
}
}
float EvaluateExpression(char *expr){
char OP[8] = {'+','-','*','/','(',')','#','\0'};
TRStack OPTR; NDStack OPND;
char *c;
char End[] = {'#','\0'};
char cc[254];
float a,b;
char theta,x;
float cf;
InitTRStack(&OPTR); TRPush(&OPTR,'#');
InitNDStack(&OPND); c = strcat(expr,End);
while(*c!='#' || TRGetTop(&OPTR)!='#') {
if(!In(*c,OP)){
while(!In(*c,OP)){strcat(cc,c);c++;}
cf = atof(cc);
OutPutTRStack(&OPTR);
OutPutNDStack(&OPND);
printf("輸入字符:%f ",cf);
memset(cc, 0x00, sizeof (char) * 256);
NDPush(&OPND,cf);
printf("操作:Push(OPND,%f)\n",cf);
}
else{
OutPutTRStack(&OPTR);
OutPutNDStack(&OPND);
printf("輸入字符:%c ",*c);
switch(Precede(TRGetTop(&OPTR),*c,OP)){
case'
TRPush(&OPTR,*c);
printf("操作:Push(OPTR,%c)\n",*c);
c++;
break;
case'=':
TRPop(&OPTR,&x);
printf("操作:Pop(OPTR,%c)\n",x);
c++;
break;
case'>':
TRPop(&OPTR,&theta);
NDPop(&OPND,&b);
NDPop(&OPND,&a);
NDPush(&OPND,Opreate(a,b,theta));
printf("操作:Opreate(%f,%c,%f)\n",a,theta,b);
break;
}
}
}
OutPutTRStack(&OPTR);
OutPutNDStack(&OPND);
printf("輸入字符:%c ",*c);
printf("操作:return GetTop(OPND)\n");
return NDGetTop(&OPND);
}
int main(){
char Exp[254];
int i = 0;
int cnt1 = 0;
int cnt2 = 0;
int flag = 0;
printf("input equation:\n");
gets(Exp);
char stdinput[17] = {'+','-','*','/','(',')','1','2','3','4','5','6','7','8','9','0','\0'};
while(Exp[i]!='\0'){
if(Exp[i]=='(') cnt1++;
if(Exp[i]==')') cnt2++;
if(!In(Exp[i],stdinput)) {flag = 1; break;}
else i++;
}
if(cnt1!=cnt2) flag = 1;
if(!flag) {printf("結果：%f",EvaluateExpression(Exp));}
else {printf("invalid input\n");}
}
總結
以上是生活随笔為你收集整理的linux算术表达式求值数据结构,数据结构：算数表达式求值演示的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 关于linux的服务器搭建,关于搭建li
- 下一篇： linux获得蓝牙外设mac,iOS获取