首页 > 代码库 > 表达式求值
表达式求值
实验5 表达式求值实验目的1． 会定义顺序栈和链栈的结点类型。2． 掌握栈的插入和删除结点在操作上的特点。3． 熟悉对栈的一些基本操作和具体的函数定义。实验内容程序1该程序的功能是实现顺序栈的定义和操作。该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。/* 定义DataType为int类型 */typedef int DataType; /* 栈的结点类型 */#define MAXSIZE 1024 typedef struct{DataType data[MAXSIZE];int top;}SeqStack; /* 初始化顺序栈 */SeqStack SeqStackInit() /* 检查顺序栈是否为空 */int SeqStackEmpty(SeqStack S) /* 把S置为空栈 */void ClearStack(SeqStack S) /* 把元素x压入栈，使其成为新的栈顶元素 */void SeqStackPush(SeqStack S,DataType x) /* 把栈顶元素弹出 */DataType SeqStackPop(SeqStack S) /* 取栈顶元素 */DataType SeqStackGetTop(SeqStack S) /*输出顺序栈中的元素*/void SeqStackPrint(SeqStack S) 程序2 用顺序栈实现算术表达式求值。将表达式看成字符串序列，输入语法正确、不含有变量的整数表达式（表达式中的数字限为单位数），利用算符的优先关系，把中序表达式转换为后序表达式后输出，然后求出该后序表达式的值。例如：输入的表达式为2*(6-4)+8/4转换后得到的后序表达式为264-*84/+设计要求：在程序中构造六个子程序分别为int empty(SeqStack stack); /*检查栈是否为空*/int operation(char op); /*判断是否为运算符*/int priority(char op); /*判断运算符的优先权*/SeqStack push(SeqStack stack,char value); /*入栈*/SeqStack pop(SeqStack stack,char *value); /*出栈*/double count(char *backorder); /*计算逆波兰表达式的值*/ 程序3 用链栈实现算术表达式求值。（与程序2的基本要求相同）链栈结点的类型描述如下：typedef int DataType;typedef struct StackNode{DataType data;struct StackNode *next;}StackNode，*LinkedStack;
“运算符优先级表” - 参考博客：http://www.jb51.net/article/37289.htm
/* 程序1该程序的功能是实现顺序栈的定义和操作。该程序包括定义的栈结构类型以及对每一种栈操作的具体的函数定义和主函数。*/#include <stdio.h>#include <stdlib.h>/* 定义DataType为int类型 */typedef int DataType; /* 栈的结点类型 */#define MAXSIZE 1024 typedef struct{ DataType data[MAXSIZE]; int top;}SeqStack; /* 初始化顺序栈 */SeqStack SeqStackInit(){ SeqStack q; q.top = -1; return q;} /* 检查顺序栈是否为空 */int SeqStackEmpty(SeqStack S){ if(S.top==-1) //栈空 return 1; else return 0;} /* 把S置为空栈 */void ClearStack(SeqStack &S){ S.top = -1;} /* 把元素x压入栈，使其成为新的栈顶元素 */void SeqStackPush(SeqStack &S,DataType x){ if(S.top==MAXSIZE-1) //已经满了 printf("入栈失败，栈已满！\n"); else { S.top++; S.data[S.top] = x; }} /* 把栈顶元素弹出 */DataType SeqStackPop(SeqStack &S){ if(S.top==-1){ //栈已空 printf("出栈失败，栈已空！\n"); return 0; } else { DataType x = S.data[S.top--]; return x; }} /* 取栈顶元素 */DataType SeqStackGetTop(SeqStack S){ return S.data[S.top];} /*输出顺序栈中的元素*/void SeqStackPrint(SeqStack S){ int top = S.top; while(top!=-1) printf("%d\n",S.data[top--]);}int Menu() //显示菜单，返回命令{ int in; printf("[1] 检查顺序栈是否为空\n"); printf("[2] 把S置为空栈\n"); printf("[3] 把元素x压入栈，使其成为新的栈顶元素\n"); printf("[4] 把栈顶元素弹出\n"); printf("[5] 取栈顶元素\n"); printf("[6] 输出顺序栈中的元素\n"); printf("[0] 按其它键退出\n"); scanf("%d",&in); return in;}void Reply(int in,SeqStack &S) //对命令的反应{ int x; switch(in){ case 1: if(SeqStackEmpty(S)) printf("栈为空！\n"); else printf("栈未空！\n"); break; case 2: ClearStack(S); //将S置为空栈 printf("已成功置为空栈！\n"); break; case 3: printf("请输入你要压栈的元素：\n"); scanf("%d",&x); SeqStackPush(S,x); break; case 4: SeqStackPop(S); break; case 5: if(SeqStackEmpty(S)) printf("栈当前为空，栈顶无元素！\n"); else printf("栈顶元素为：%d\n",SeqStackGetTop(S)); break; case 6: if(SeqStackEmpty(S)) printf("栈当前为空！\n"); else{ printf("栈中元素为（从顶至下）：\n"); SeqStackPrint(S); } break; default: exit(1); } system("pause"); system("cls");}int main(){ SeqStack S = SeqStackInit(); while(1){ int in = Menu(); Reply(in,S); } return 0;}
1 /* 程序2 用顺序栈实现算术表达式求值。 2 将表达式看成字符串序列，输入语法正确、不含有变量的整数表达式（表达式中的数字限为单位数） 3 利用算符的优先关系，把中序表达式转换为后序表达式后输出，然后求出该后序表达式的值。 4 例如：输入的表达式为2*(6-4)+8/4 5 转换后得到的后序表达式为264-*84/+ 6 设计要求：在程序中构造六个子程序分别为 7 */ 8 #include <stdio.h> 9 #include <stdlib.h> 10 /* 定义DataType为int类型 */ 11 typedef char DataType; 12 13 /* 栈的结点类型 */ 14 #define MAXSIZE 1024 15 typedef struct{ 16 char data[MAXSIZE]; 17 int top; 18 }SeqStack; 19 SeqStack op; //运算符栈和表达式栈 20 21 int Prior[6][6] = //Prior[lop][rop] 22 { // 运算符优先级表 23 // ‘+‘ ‘-‘ ‘*‘ ‘/‘ ‘(‘ ‘)‘ 24 /*‘+‘*/-1,-1,1,1,1,-1, 25 /*‘-‘*/-1,-1,1,1,1,-1, 26 /*‘*‘*/-1,-1,-1,-1,1,-1, 27 /*‘/‘*/-1,-1,-1,-1,1,-1, 28 /*‘(‘*/1,1,1,1,1,0, 29 /*‘)‘*/-1,-1,-1,-1,0,-1 30 }; 31 32 int empty(SeqStack stack) /*检查栈是否为空*/ 33 { 34 if(stack.top==-1) //栈空 35 return 1; 36 else 37 return 0; 38 } 39 int operation(char op) /*判断是否为运算符*/ 40 { 41 if(‘0‘<=op && op<=‘9‘) //是单位数字，不是运算符 42 return 0; 43 else 44 return 1; 45 } 46 int priority(char rop) /*判断运算符的优先权*/ 47 { 48 char lop = op.data[op.top]; 49 int a,b; 50 switch(lop){ 51 case ‘+‘:a=0;break; 52 case ‘-‘:a=1;break; 53 case ‘*‘:a=2;break; 54 case ‘/‘:a=3;break; 55 case ‘(‘:a=4;break; 56 case ‘)‘:a=5;break; 57 default:break; 58 } 59 switch(rop){ 60 case ‘+‘:b=0;break; 61 case ‘-‘:b=1;break; 62 case ‘*‘:b=2;break; 63 case ‘/‘:b=3;break; 64 case ‘(‘:b=4;break; 65 case ‘)‘:b=5;break; 66 default:break; 67 } 68 return Prior[a][b]; 69 } 70 SeqStack push(SeqStack stack,char value) /*入栈*/ 71 { 72 if(stack.top==MAXSIZE-1) //已经满了 73 printf("入栈失败，栈已满！\n"); 74 else { 75 stack.top++; 76 stack.data[stack.top] = value; 77 } 78 return stack; 79 } 80 SeqStack pop(SeqStack stack,char *value) /*出栈*/ 81 { 82 if(stack.top==-1){ //栈已空 83 printf("出栈失败，栈已空！\n"); 84 return stack; 85 } 86 else { 87 *value = http://www.mamicode.com/stack.data[stack.top--]; 88 return stack; 89 } 90 } 91 double count(char *backorder) /*计算逆波兰表达式的值*/ 92 { 93 struct { 94 double data[MAXSIZE]; 95 int top; 96 } ds; //数栈 97 ds.top = -1; 98 int i; 99 for(i=0;backorder[i];i++)100 if(operation(backorder[i])){ //是运算符101 double a,b;102 b = ds.data[ds.top--]; //从数栈中依次取出两个数103 a = ds.data[ds.top--];104 switch(backorder[i]){ //运算并入栈105 case ‘+‘:ds.top++;ds.data[ds.top] = a+b;break;106 case ‘-‘:ds.top++;ds.data[ds.top] = a-b;break;107 case ‘*‘:ds.top++;ds.data[ds.top] = a*b;break;108 case ‘/‘:ds.top++;ds.data[ds.top] = a/b;break;109 default:break;110 }111 }112 else{ //是数，直接入数栈113 ds.top++;114 ds.data[ds.top] = double(backorder[i] - ‘0‘);115 }116 return ds.data[ds.top];117 }118 void trans(char exp[],char backorder[]) //将中序表达式转换成后缀表达式，存储一字符串中119 {120 int index=0;121 int len = 0;122 while(exp[index]){123 if(operation(exp[index])){ //是运算符124 if(empty(op)){ //如果运算符栈为空，直接入栈125 op = push(op,exp[index++]);126 }127 else{ //运算符栈不为空，与将该运算符与栈顶运算符比较128 char c;129 switch(priority(exp[index])){130 case 1: //当前运算符比栈顶运算符优先级高131 op = push(op,exp[index++]);132 break;133 case 0: //运算符优先级相等。只出现在栈顶为‘(‘和当前为‘)‘的情况134 op = pop(op,&c);135 index++;136 break;137 case -1: //当前运算符优先级低138 op = pop(op,&c); //退栈 139 backorder[len++] = c; //将运算符放入字符串中140 break;141 default:break;142 }143 }144 }145 else{ //是数字。直接压栈146 backorder[len++] = exp[index++]; //将数字放入字符串中147 }148 }149 while(!empty(op)){ //如果运算符栈不为空，全部出栈150 char c;151 op = pop(op,&c); //退栈 152 backorder[len++] = c; //将运算符放入字符串中153 }154 backorder[len] = ‘\0‘;155 }156 void print(char backorder[]) //输出表达式栈中的式子157 {158 int i;159 for(i=0;backorder[i];i++)160 printf("%c",backorder[i]);161 printf("\n");162 }163 int main()164 {165 char exp[MAXSIZE];166 char backorder[MAXSIZE];167 printf("[1] 请输入中缀表达式：\n");168 while(scanf("%s",exp)!=EOF){169 //初始化170 op.top = -1;171 //输出转换后的后缀表达式172 trans(exp,backorder);173 printf("[2] 其后缀表达式为：\n");174 print(backorder);175 //计算后缀表达式的结果176 printf("[3] 后缀表达式的结果：\n");177 printf("%lf\n",count(backorder));178 //为下一次输入做准备179 printf("\n");180 printf("请输入中缀表达式：\n");181 }182 return 0;183 }
1 /* 程序3 用链栈实现算术表达式求值。（与程序2的基本要求相同） 2 */ 3 #include <stdio.h> 4 #include <stdlib.h> 5 6 /* 栈的结点类型 */ 7 #define MAXSIZE 1024 8 9 //链栈结点的类型描述如下： 10 typedef char DataType; 11 typedef struct StackNode{ 12 DataType data; 13 struct StackNode *next; 14 } StackNode,*LinkedStack; 15 16 LinkedStack op; //运算符栈和表达式栈 17 18 int Prior[6][6] = //Prior[lop][rop] 19 { // 运算符优先级表 20 // ‘+‘ ‘-‘ ‘*‘ ‘/‘ ‘(‘ ‘)‘ 21 /*‘+‘*/-1,-1,1,1,1,-1, 22 /*‘-‘*/-1,-1,1,1,1,-1, 23 /*‘*‘*/-1,-1,-1,-1,1,-1, 24 /*‘/‘*/-1,-1,-1,-1,1,-1, 25 /*‘(‘*/1,1,1,1,1,0, 26 /*‘)‘*/-1,-1,-1,-1,0,-1 27 }; 28 29 int empty(LinkedStack &stack) /*检查栈是否为空*/ 30 { 31 if(stack->next==NULL) //栈空 32 return 1; 33 else 34 return 0; 35 } 36 int operation(char op) /*判断是否为运算符*/ 37 { 38 if(‘0‘<=op && op<=‘9‘) //是单位数字，不是运算符 39 return 0; 40 else 41 return 1; 42 } 43 int priority(char rop) /*判断运算符的优先权*/ 44 { 45 char lop = op->next->data; 46 int a,b; 47 switch(lop){ 48 case ‘+‘:a=0;break; 49 case ‘-‘:a=1;break; 50 case ‘*‘:a=2;break; 51 case ‘/‘:a=3;break; 52 case ‘(‘:a=4;break; 53 case ‘)‘:a=5;break; 54 default:break; 55 } 56 switch(rop){ 57 case ‘+‘:b=0;break; 58 case ‘-‘:b=1;break; 59 case ‘*‘:b=2;break; 60 case ‘/‘:b=3;break; 61 case ‘(‘:b=4;break; 62 case ‘)‘:b=5;break; 63 default:break; 64 } 65 return Prior[a][b]; 66 } 67 LinkedStack push(LinkedStack &stack,char value) /*入栈*/ 68 { 69 LinkedStack p = (LinkedStack)malloc(sizeof(StackNode)); 70 p->data =http://www.mamicode.com/ value; 71 p->next = stack->next; 72 stack->next = p; 73 return stack; 74 } 75 LinkedStack pop(LinkedStack &stack,char *value) /*出栈*/ 76 { 77 if(stack->next==NULL){ //栈已空 78 printf("出栈失败，栈已空！\n"); 79 return stack; 80 } 81 else { 82 LinkedStack p = stack->next; 83 stack->next = p->next; 84 *value = http://www.mamicode.com/p->data; 85 free(p); 86 return stack; 87 } 88 } 89 double count(char *backorder) /*计算逆波兰表达式的值*/ 90 { 91 typedef struct DigitStack{ 92 double data; 93 DigitStack *next; 94 } DigitStack,*LinkedDS; //数栈 95 LinkedDS ds = (LinkedDS)malloc(sizeof(DigitStack)); 96 LinkedDS p; 97 ds->next = NULL; //初始化 98 int i; 99 for(i=0;backorder[i];i++)100 if(operation(backorder[i])){ //是运算符101 double a,b;102 p = ds->next; //从数栈中依次取出两个数103 ds->next = p->next;104 b = p->data;105 free(p);106 p = ds->next;107 ds->next = p->next;108 a = p->data;109 free(p);110 p = (LinkedDS)malloc(sizeof(DigitStack));111 switch(backorder[i]){ //运算并入栈112 case ‘+‘:113 p->data = http://www.mamicode.com/a+b;114 p->next = ds->next;115 ds->next = p;116 break;117 case ‘-‘:118 p->data = http://www.mamicode.com/a-b;119 p->next = ds->next;120 ds->next = p;121 break;122 case ‘*‘:123 p->data = http://www.mamicode.com/a*b;124 p->next = ds->next;125 ds->next = p;126 break;127 case ‘/‘:128 p->data = http://www.mamicode.com/a/b;129 p->next = ds->next;130 ds->next = p;131 break;132 default:break;133 }134 }135 else{ //是数，直接入数栈136 p = (LinkedDS)malloc(sizeof(DigitStack));137 p->data = http://www.mamicode.com/double(backorder[i] - ‘0‘);138 p->next = ds->next;139 ds->next = p;140 }141 return ds->next->data;142 }143 void trans(char exp[],char backorder[]) //将中序表达式转换成后缀表达式，存储一字符串中144 {145 int index=0;146 int len = 0;147 while(exp[index]){148 if(operation(exp[index])){ //是运算符149 if(empty(op)){ //如果运算符栈为空，直接入栈150 op = push(op,exp[index++]);151 }152 else{ //运算符栈不为空，与将该运算符与栈顶运算符比较153 char c;154 switch(priority(exp[index])){155 case 1: //当前运算符比栈顶运算符优先级高156 op = push(op,exp[index++]);157 break;158 case 0: //运算符优先级相等。只出现在栈顶为‘(‘和当前为‘)‘的情况159 op = pop(op,&c);160 index++;161 break;162 case -1: //当前运算符优先级低163 op = pop(op,&c); //退栈 164 backorder[len++] = c; //将运算符放入字符串中165 break;166 default:break;167 }168 }169 }170 else{ //是数字。直接压栈171 backorder[len++] = exp[index++]; //将数字放入字符串中172 }173 }174 while(!empty(op)){ //如果运算符栈不为空，全部出栈175 char c;176 op = pop(op,&c); //退栈 177 backorder[len++] = c; //将运算符放入字符串中178 }179 backorder[len] = ‘\0‘;180 }181 void print(char backorder[]) //输出表达式栈中的式子182 {183 int i;184 for(i=0;backorder[i];i++)185 printf("%c",backorder[i]);186 printf("\n");187 }188 void Destroy(LinkedStack &op)189 {190 while(op->next){191 LinkedStack p = op->next;192 op->next = p->next;193 free(p);194 }195 }196 int main()197 {198 char exp[MAXSIZE];199 char backorder[MAXSIZE];200 op = (LinkedStack)malloc(sizeof(StackNode));201 printf("[1] 请输入中缀表达式：\n");202 while(scanf("%s",exp)!=EOF){203 //初始化204 op->next = NULL;205 //输出转换后的后缀表达式206 trans(exp,backorder);207 printf("[2] 其后缀表达式为：\n");208 print(backorder);209 //计算后缀表达式的结果210 printf("[3] 后缀表达式的结果：\n");211 printf("%lf\n",count(backorder));212 //为下一次输入做准备213 Destroy(op);214 printf("\n");215 printf("请输入中缀表达式：\n");216 }217 return 0;218 }
表达式求值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。