实验二栈和队列 实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构,以便在实际背景下 灵活运用 握栈和队列的特点,即先进后出与先进先出的原则 3、栈和队列的基本运算,如入栈和出栈、入队与出队等运算在顺序存 储结构和链式存储结构上的实现。 二、实验内容 1、表达式求值 [问题描述]表达式求值是程序设计语言编译中的一个基本算法。他的 实现是栈应用的一个典型例子。这里采用较为流行的“算符优先法”来实现 对表达式的求值。要把一个表达式翻译成正确求值的一个机器指令序列,或 者是直接对表达式求值,首先要能够正确解释表达式。那么就要了解算术四 则运算的基本规则 1)先乘除,后加减 2)从左算到右 4)先括号内,后括号外。 例如表达式:4+2*3-10/5的计算顺序为: 4+2*3-10/5=4+6-10/5=10-10/5=10-2=8 算符优先法就是根据这个运算优先关系的规则来实现对表达式的编译或解 释执行的。 [基本要求]要求能根据算符优先法则对所输入的四则运算表达进行求 值 [实现提示]任何表达式都由操作数、运算符、定界符组成,我们把运 算符和定界符统称为算符。它们构成的集合命名为ΦP,根据运算法则在每 步中,任意两个算符优先级关系可以由下表来描述 Q2 幸() >><< >>>><> >>>> <> <<<<< <<<< 其中,Q1<Q2Q1的优先级低于Q2 Q1=Q2Q1的优先级等于Q2
实验二 栈和队列 一、 实验目的 1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下 灵活运用。 2、 握栈和队列的特点，即先进后出与先进先出的原则。 3、栈和队列的基本运算，如入栈和出栈、入队与出队等运算在顺序存 储结构和链式存储结构上的实现。 二、实验内容 1、表达式求值 [问题描述] 表达式求值是程序设计语言编译中的一个基本算法。他的 实现是栈应用的一个典型例子。这里采用较为流行的“算符优先法”来实现 对表达式的求值。要把一个表达式翻译成正确求值的一个机器指令序列，或 者是直接对表达式求值，首先要能够正确解释表达式。那么就要了解算术四 则运算的基本规则： 1）先乘除，后加减； 2）从左算到右； 4）先括号内，后括号外。 例如表达式：4+2*3-10/5 的计算顺序为： 4+2*3–10/5=4+6–10/5=10–10/5=10–2=8 算符优先法就是根据这个运算优先关系的规则来实现对表达式的编译或解 释执行的。 [基本要求] 要求能根据算符优先法则对所输入的四则运算表达进行求 值。 [实现提示] 任何表达式都由操作数、运算符、定界符组成，我们把运 算符和定界符统称为算符。它们构成的集合命名为 OP，根据运算法则在每 一步中，任意两个算符优先级关系可以由下表来描述: 其中， Q1<Q2 Q1 的优先级低于 Q2 Q1=Q2 Q1 的优先级等于 Q2
Q1>Q2Q1的优先级高于Q2 “#”号表示表达式的开始与结東 该表可以采用二维表表示,由先后两算符的序号做下标定位两者的优先 级,如“*”的序号为2,“+”的序号为1,则“*”与“+”相遇OP[2,1] 得到“>”所以“*”的优先级高 [程序实现] (1)算法思想 为了实现算符优先算法,可以使用两个工作栈,一个是操作数栈OPDS, 另一个是运算符栈oPS,分别存放操作数与算符。首先将标志“#”进运算 符栈OPS的底,按照栈后进先出的原则进行: 遇到操作数,进操作数栈,计算机继续扫描下一符号 遇到运算符时,需要将此算符的优先级与OPS栈顶算符优先级比 若优先级比站顶元素高,则进OPS栈,继续扫描下一符号 若优先级比站顶元素低,则运算符优先级比站顶元素OPS栈顶 元素退栈形成一个操作码Q:同时,操作数栈OPS两次退栈 形成两个操作数a,b.计算机对操作数与操作码完成一次运算 操作,即aQb.其运算结果存放在操作数OPDS栈,作为一次运 算的中间结果进OPDS栈。 ≯若与栈OPS栈顶元素优先级相等,则栈顶元素退栈。当遇到栈 顶元素是“#”时,表示整个运算结果,否则,继续扫描下一 个符号 (2)程序实现 /*初始化* ALsE O #define true 1 #define max 10 #include <stdio. h> #include <stdlib. h> void push opds (: / *push opds stack. * float pop opds(: /=pop opds stack. * void push ops o: /=push ops stack. * float pop ops o: /pop ops stack. * char relation(:/*>,<,=*/ float operate: /*+ - *, /* float opds [MAX int ops [MAX /* operator’ s stack*/ int topd=O
Q1>Q2 Q1 的优先级高于 Q2 “#”号表示表达式的开始与结束。 该表可以采用二维表表示，由先后两算符的序号做下标定位两者的优先 级，如“*”的序号为 2，“+”的序号为 1，则“*”与“+”相遇 OP[2，1] 得到“>”所以“*”的优先级高。 [程序实现] （1） 算法思想 为了实现算符优先算法，可以使用两个工作栈，一个是操作数栈 OPDS， 另一个是运算符栈 OPS，分别存放操作数与算符。首先将标志“#”进运算 符栈 OPS 的底，按照栈后进先出的原则进行： ◆ 遇到操作数，进操作数栈，计算机继续扫描下一符号； ◆ 遇到运算符时，需要将此算符的优先级与 OPS 栈顶算符优先级比 较。 ➢ 若优先级比站顶元素高，则进 OPS 栈，继续扫描下一符号； ➢ 若优先级比站顶元素低，则运算符优先级比站顶元素 OPS 栈顶 元素退栈形成一个操作码 Q；同时，操作数栈 OPDS 两次退栈， 形成两个操作数 a,b.计算机对操作数与操作码完成一次运算 操作，即 aQb.其运算结果存放在操作数 OPDS 栈，作为一次运 算的中间结果进 OPDS 栈。 ➢ 若与栈 OPS 栈顶元素优先级相等，则栈顶元素退栈。当遇到栈 顶元素是“#”时，表示整个运算结果，否则，继续扫描下一 个符号。 （2） 程序实现 /* 初始化*/ #define FALSE 0 #define TRUE 1 #define MAX 10 #include <stdio.h> #include <stdlib.h> void push_opds(); /*push opds stack.*/ float pop_opds(); /*pop opds stack.*/ void push_ops(); /*push ops stack.*/ float pop_ops(); /*pop ops stack.*/ char relation(); /*>,<,=*/ float operate(); /*+,-,*,/*/ float opds[MAX]; /*operand's stack */ int ops[MAX]; /*operator's stack */ int topd=0; /*opds's top*/
/*主函数,表达式求值 void maino char sy flo rinf ("\n Please input expression(# end): \n") sh ops(#') ymb=getchar o while((symb!=#)I((char)(ops[top)!=#)) if((symb!=+)&&(symb!=-)&&(symb!=’*)&&(symb!=/)&&(s ymb!=()&(symb!=)’)&&(symb!=#)&&(symb!=)) /*不是算符,则是操作数进OPDS栈 push opds(symb se /*是算符,先比较优先级,在分情况处理 ch=relation((char)(ops [top]), symb) switch(ch) case case s topd=topd+1: / *push opds stack*/
int top=0; /*opd's top*/ char symb; /*主函数，表达式求值 void main() { char sy; char ch; float a,b; printf("\n Please input expression(# end):\n"); push_ops('#'); symb=getchar(); while ((symb!='#')||((char)(ops[top])!='#')) { if((symb!='+')&&(symb!='-')&&(symb!='*')&&(symb!='/')&&(s ymb!='(')&&(symb!=')')&&(symb!='#')&&(symb!=' ')) { /*不是算符，则是操作数进 OPDS 栈 push_opds(symb); symb=getchar(); } else { /*是算符，先比较优先级，在分情况处理 ch=relation((char)(ops[top]),symb); switch(ch) { case '<': push_ops(symb); symb=getchar(); break; case '=': sy=pop_ops(); symb=getchar(); break; case '>': sy=pop_ops(); b=pop_opds(); a=pop_opds(); topd=topd+1; /*push_opds stack*/ opds[topd]=operate(a,sy,b);
printf(error\n") printf("\nThe result=%1. 2f\n", opds [topd]); retch /*操作数压栈 void push opds(ch) char c int ch if (topd==MAX-1) printf( the opds stack is overflow. \n") else chi=ch-’0’;/*将字符转化为“值”:“3”转为3 opds [topd]=ch i /*操作数弹栈 float pop opds o return (opds [topd+1]) /*操作符压栈 void push ops (ch) cnal printf( the ops stack is overflow. \ n") else top++:
break; case ' ': printf("error\n"); break; } } } printf("\nThe result=%1.2f\n",opds[topd]); getch(); } /*操作数压栈 void push_opds(ch) char ch; { int ch_i; if (topd==MAX-1) printf("the opds stack is overflow.\n"); else { ch_i=ch-'0'; /*将字符转化为“值”：“3”转为 3 topd++; opds[topd]=ch_i; } } /*操作数弹栈 float pop_opds() { topd=topd-1; return(opds[topd+1]); } /*操作符压栈 void push_ops(ch) char ch; { if (top==MAX-1) printf("the ops stack is overflow.\n"); else { top++;
ops[top]=(int)(ch) /*操作符弹栈 t return((char)(ops [top+1])) /*比较两个算符sym1,sym2的优先关系 char relation(syml, sym2) char chl[2] int ind [2] char re[7][7={{>,>,’<’,’<,<,’>’,”〉}, ”>,’〉’,〉’,’〉,’<,”〉,”》}, (”>,”〉’,”〉’,〉’,’<’,”〉,”〉}, ”,,, <’,’<,”<,<,<, chl[oj=syml for(i=0;i<=1;i++) switch(chl[il) case '+: ind[i]=0; break ind[i]=l: break case '*t: ind[i]=2; break; case/: ind[i]=3: break case(: ind[i]=4; break case#: ind[i]6: break default: printf ("error\n"): return(0')
ops[top]=(int)(ch); } } /*操作符弹栈 float pop_ops() { top=top-1; return((char)(ops[top+1])); } /*比较两个算符 sym1,sym2 的优先关系 char relation(sym1,sym2) char sym1,sym2; { int i; char chl[2]; int ind[2]; char re[7][7]={ {'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=',' '}, {'>','>','>','>',' ','>','>'}, {'<','<','<','<','<',' ','='}}; chl[0]=sym1; chl[1]=sym2; for (i=0;i<=1;i++) { switch(chl[i]) { case '+': ind[i]=0;break; case '-': ind[i]=1;break; case '*': ind[i]=2;break; case '/': ind[i]=3;break; case '(': ind[i]=4;break; case ')': ind[i]=5;break; case '#': ind[i]=6;break; default:printf("error\n");return('0'); }