数据结构表达式的两种计算方法
一、设计思想
（一）先将输入的中缀表达式转为后缀再计算的设计思想
我们所熟知的计算表达式为中缀表达式，这之中包含运算符的优先级还有括号，这对我们来说已经习以为常了，但是在计算机看来，这是非常复杂的一种表达式。因此我们需要有一种更能使计算机理解的不用考虑优先级也不包括括号的表达式，也就是后缀表达式。我们可以借助栈将其实现。
首先，我们需要将中缀表达式转换为后缀表达式，这也是这个算法的关键之处。我们将创建两个栈，一个是字符型的，用来存放操作符；另一个是浮点型的，存放操作数。
接着，开始扫描输入的表达式，如果是操作数直接进入一个存放后缀表达式的数组，而操作符则按照优先级push进栈（加减为1，乘除为2），若当前操作符优先级大于栈顶操作符优先级或栈为空，push进栈，而当其优先级小于等于栈顶操作符优先级，则从栈内不断pop出操作符并进入后缀表达式数组，直到满足条件，当前操作符才能push 进栈。左括号无条件入栈，右括号不入栈，而不断从栈顶pop出操作符进入后缀表达式数组，直到遇到左括号后，将其pop出栈。这样当扫描完输入表达式并从操作符栈pop 出残余操作符后并push进栈，后缀表达式数组中存放的就是我们所需要的后缀表达式了。
扫描后缀表达式数组，若是操作数，将其转换为浮点型push进数栈；若是操作符，则连续从数栈中pop出两个数做相应运算，将结果push进数栈。当扫描完数组后，数栈顶便为最终结果，将其pop出，输出结果。
（二）一边扫描一边计算的设计思想
由于第一种算法需要进行两遍扫描，因此在性能上不会十分优秀。而此种算法只用扫描一遍，当扫描完输入的表达式后便可以直接输出最终结果。是第一种算法的改进版，性能上也得到提升，与第一种算法所不同的是其需要同时使用两个栈，一个操作符栈，一个数栈。
当扫描表达式时，若是操作数则将其转换为浮点型后直接push进数栈，而若是操作符则按照优先级规则push进操作符栈（加减为1，乘除为2），若当前操作符优先级大于栈顶操作符优先级或栈为空，push进栈，而当其优先级小于等于栈顶操作符优先级，则从栈内不断pop出操作符，直到满足条件，当前操作符才能push进栈。左括号无条件入栈，右括号不入栈，而不断从栈顶pop出操作符，直到遇到左括号后，将其pop出栈。这中间pop出操作符后直接从数栈中pop出两个数并计算，将结果push进数栈。括号的处理与第一个算法相同。
扫描完成后，从操作符栈pop出残余操作符，从数栈中pop出两个数并计算并进行计算，将结果push进数栈。数栈顶便为最终结果，将其pop出，输出结果。
两种算法各有各的优缺点，第一种算法过程比较清晰，使我们能够更加容易理解栈的使用规则，但是其性能不如第二种。第二种算法相比第一种来说性能提高了，但是理解起来就不如第一种那么清晰了。
二、算法流程图
以下是先将输入的中缀表达式转为后缀再计算算法：
图1 中缀转后缀算法流程图
以下是一边扫描一边计算算法：
图2一边扫描一边计算算法流程图三、源代码
以下为先将输入的中缀表达式转为后缀再计算算法代码：#include "stdio.h"
#include "stdlib.h"
/*定义存放操作符的结构体*/
struct OpStrack
{
char op[100];/*存放操作符的数组*/
int top;/*栈顶索引*/
int level[100];/*存放操作符优先级的数组*/
}OpStrackArray;
/*定义存放语素的结构体*/
struct OdStrack
{
float od[100];/*存放操作数的数组*/
int top;/*栈顶索引*/
}OdStrackArray;
/*声明需要用到的函数*/
int judge(char,char[],int,int);
int stackIsEmpty();
void pushOp(char,int);
char popOp();
void pushOd(float);
float popOd();
void compute(char);
/*主函数*/
void main()
{
char data[100];/*声明存放中缀表达式的字符串*/
char tempdata[200];/*声明存放后缀表达式的字符串*/
int i=0;/*作为遍历字符串的索引*/
int j=0;/*作为输出后缀表达式的索引*/
int z=0;/*作为存放后缀表达式的索引*/
int k=0;/*作为将后缀表达式赋给临时转float的索引*/
int eq=0;/*判断括号是否正确的条件*/
float result;/*声明存放最终结果的float*/
scanf("%s",data);/*输入中缀表达式*/
/*中缀转后缀，并将结果放入tempdata*/
while(data[i]!='\0')
{
if((data[i]>='0'&&data[i]<='9')||data[i]=='.')/*如果是语素则存放至temp数组*/
{
tempdata[z]=data[i];
z++;
}
else
{
switch(data[i])
{
case '+':
z+=judge(data[i],tempdata,i,1);
break;
case '-':
z+=judge(data[i],tempdata,i,1);/*加减优先级为1*/
break;
case '*':
z+=judge(data[i],tempdata,i,2);/*乘除优先级为2*/
break;
case '/':
/*返回出栈操作符的数量，以便将z索引向后推相应步*/
z+=judge(data[i],tempdata,i,2);
break;
case '(':
pushOp(data[i],-1);/*'('直接入栈，但入栈后优先级最小*/
eq++;/*有一个'('eq+1*/
break;
case ')':
while(OpStrackArray.op[OpStrackArray.top-1]!='(')/*')'不入栈*/
{
/*不断弹出操作符并进入后缀表达式数组，直到遇到'('*/
tempdata[z]=popOp();
z++;/*索引+1*/
/*如果发现还没碰到与之匹配的'('时栈已空则说明表达式不合法*/ if(stackIsEmpty()==1)
{
printf("Expression is not valid!Press any key to continue...");
getch();
return;
}
}
popOp();/*弹出'('*/
eq--;/*如有与'('配队的')'则eq-1*/
break;
}
}
i++;
}
if(eq!=0)/*如果eq!=0说明'('与')'不能完全配队，输入的表达式不合法*/
{
printf("Expression is not valid!Press any key to continue...");
getch();
return;
}
/*将操作符栈内存留的操作符放入tempdata*/
while(stackIsEmpty()==0)
{
/*如果操作符栈不空则不断弹出操作符并进入后缀表达式数组*/
tempdata[z]=popOp();
z++;
}
/*扫描后缀表达式，计算后放入操作数栈*/
while(k { char temp[20]={'\0'};/*声明临时的存放操作数的数组并附初值*/ int t=0;/*作为temp数组的索引*/ float f;/*存放转换为float的数*/ /*如果是语素则存放至temp数组*/ while((tempdata[k]>='0'&&tempdata[k]<='9')||tempdata[k]=='.') { temp[t]=tempdata[k]; k++; t++; } if(temp[0]!='\0')/*判断temp数组是否为空，是则将其转换为float并压栈*/ { f=atof(temp);/*字符串转float*/ pushOd(f);/*操作数入栈*/ } if(tempdata[k]=='+'||tempdata[k]=='-'||tempdata[k]=='*'||tempdata[k]=='/') { compute(tempdata[k]);/*如果扫描到操作符则作相应计算*/ } k++; } /*输出后缀表达式*/ printf("The postfix expression is:"); for(j=0;j { printf("%c",tempdata[j]); } printf("\n"); /*从操作数栈内弹出最终结果并输出*/ result=popOd(); printf("The result is:%.2f",result);/*结果取两位小数*/ printf("\n"); printf("Press any key to continue..."); getch(); } /*判断操作符优先级并作出相应处理，返回出栈操作符数量*/ int judge(char op,char tempdata[],int index,int level) { int cont=0; if(stackIsEmpty()==1||OpStrackArray.level[OpStrackArray.top-1] { /*如果栈为空或栈顶操作符优先级小于当前操作符优先级则将其压栈*/ pushOp(op,level); cont++;/*使z索引向后推1*/ } else { while(stackIsEmpty()!=1&&OpStrackArray.level[OpStrackArray.top-1]>=level) { /*操作符不断出栈并入后缀表达式数组直到栈为空或栈顶操作符优先级大于等于当前操 作符优先级*/ tempdata[index]=popOp(); index++;/*后缀表达式数组索引+1*/ cont++;/*出栈操作符数量+1*/ } pushOp(op,level);/*将当前操作符压栈*/ } return cont; } /*判断操作符栈是否为空，是则返回1，否返回0*/ int stackIsEmpty() { if(OpStrackArray.op[0]=='\0') { return 1; } return 0; } /*将操作符压入栈*/ void pushOp(char op,int level) { OpStrackArray.op[OpStrackArray.top]=op;/*操作符进入数组*/ OpStrackArray.level[OpStrackArray.top]=level;/*为对应操作符附优先级*/ OpStrackArray.top++;/*top索引+1*/ } /*操作符出栈，返回栈顶操作符*/ char popOp() { char c=OpStrackArray.op[OpStrackArray.top-1];/*取得栈顶操作符*/ OpStrackArray.op[OpStrackArray.top-1]='\0'; /*分别将op数组与level数组还原为默认值*/ OpStrackArray.level[OpStrackArray.top-1]=0; OpStrackArray.top--;/*top索引-1*/ return c;/*返回栈顶操作符*/ } /*将操作数压入栈*/ void pushOd(float f) { OdStrackArray.od[OdStrackArray.top]=f;/*操作数进入数组*/ OdStrackArray.top++;/*top索引+1*/ } /*操作符出栈，返回栈顶操作数*/ float popOd() { float f=OdStrackArray.od[OdStrackArray.top-1];/*取得栈顶操作数*/ OdStrackArray.od[OdStrackArray.top-1]=0.0;/*将od数组还原为默认值*/ OdStrackArray.top--;/*top索引-1*/ return f;/*返回栈顶操作数*/ } /*根据传入操作符运算，并将结果压入操作数栈*/ void compute(char op) { float tempresult;/*临时计算结果*/ float od1=popOd(); float od2=popOd();/*连续pop出两个操作数*/ switch(op)/*根据传入操作符计算*/ { case '+': tempresult=od2+od1; break; case '-': tempresult=od2-od1; break; case '*': tempresult=od2*od1; break; case '/': tempresult=od2/od1; break; } pushOd(tempresult);/*将计算结果压栈*/ } 以下为一边扫描一边计算算法代码： #include "stdio.h" #include "stdlib.h" /*定义存放操作符的结构体*/ struct OpStrack { char op[100];/*存放操作符的数组*/ int top;/*栈顶索引*/ int level[100];/*存放操作符优先级的数组*/ }OpStrackArray; /*定义存放语素的结构体*/ struct OdStrack { float od[100];/*存放操作数的数组*/ int top;/*栈顶索引*/ }OdStrackArray; /*声明需要用到的函数*/ void pushOp(char,int); char popOp(); void pushOd(float); float popOd(); int stackIsEmpty(); void judge(char,int); void compute(char); /*主函数*/ void main() { char data[100];/*声明存放中缀表达式的字符串*/ int i=0;/*作为遍历字符串的索引*/ int eq=0;/*判断括号是否正确的条件*/ float result;/*声明存放最终结果的float*/ scanf("%s",data);/*输入中缀表达式*/ /*扫描输入的表达式并作出相应处理*/ while(data[i]!='\0') { char temp[20]={'\0'};/*声明临时的存放操作数的数组并附初值*/ int j=0;/*作为temp数组的索引*/ float f;/*存放转换为float的数*/ while((data[i]>='0'&&data[i]<='9')||data[i]=='.')/*如果是语素则存放至temp数组*/ { temp[j]=data[i]; j++; i++; } if(temp[0]!='\0')/*判断temp数组是否为空，是则将其转换为float并压栈*/ { f=atof(temp);/*字符串转float*/ pushOd(f);/*操作数入栈*/ } switch(data[i]) { case '+': judge(data[i],1); break; case '-': judge(data[i],1);/*加减优先级为1*/ break; case '*': judge(data[i],2); break; case '/': judge(data[i],2);/*乘除优先级为2*/ break; case '(': pushOp(data[i],-1);/*'('直接入栈，但入栈后优先级最小*/ eq++;/*有一个'('eq+1*/ break; case ')': while(OpStrackArray.op[OpStrackArray.top-1]!='(')/*')'不入栈*/ { compute(popOp());/*不断弹出操作符并计算，直到遇到'('*/ /*如果发现还没碰到与之匹配的'('时栈已空则说明表达式不合法*/ if(stackIsEmpty()==1)/ { printf("Expression is not valid!Press any key to continue..."); getch(); return; } } popOp();/*弹出'('*/ eq--;/*如有与'('配队的')'则eq-1*/ break; } i++; } /*扫描操作符栈内残余操作符并做相应计算*/ while(stackIsEmpty()==0) { compute(popOp());/*如果操作符栈不空则弹出操作符并计算*/ } /*从操作数栈内弹出最终结果并输出*/ if(eq==0)/*如果eq=0说明'('与')'可以完全配队，输入的表达式合法*/ { result=popOd(); printf("The result is:%.2f",result);/*结果取两位小数*/ } else/*如果eq!=0说明'('与')'不能完全配队，输入的表达式不合法*/ { printf("Expression is not valid!Press any key to continue..."); } printf("\n"); printf("Press any key to continue..."); getch(); } /*将操作符压入栈*/ void pushOp(char op,int level) { OpStrackArray.op[OpStrackArray.top]=op;/*操作符进入数组*/ OpStrackArray.level[OpStrackArray.top]=level;/*为对应操作符附优先级*/ OpStrackArray.top++;/*top索引+1*/ } /*操作符出栈，返回栈顶操作符*/ char popOp() { char c=OpStrackArray.op[OpStrackArray.top-1];/*取得栈顶操作符*/ OpStrackArray.op[OpStrackArray.top-1]='\0'; OpStrackArray.level[OpStrackArray.top-1]=0;/*分别将op数组与level数组还原为默认值*/ OpStrackArray.top--;/*top索引-1*/ return c;/*返回栈顶操作符*/ } /*将操作数压入栈*/ void pushOd(float f) { OdStrackArray.od[OdStrackArray.top]=f;/*操作数进入数组*/ OdStrackArray.top++;/*top索引+1*/ } /*操作符出栈，返回栈顶操作数*/ float popOd() { float f=OdStrackArray.od[OdStrackArray.top-1];/*取得栈顶操作数*/ OdStrackArray.od[OdStrackArray.top-1]=0.0;/*将od数组还原为默认值*/ OdStrackArray.top--;/*top索引-1*/ return f;/*返回栈顶操作数*/ } /*判断操作符栈是否为空，是则返回1，否返回0*/ int stackIsEmpty() { if(OpStrackArray.op[0]=='\0') { return 1; } return 0; } /*判断操作符优先级作出相应处理*/ void judge(char op,int level) { if(stackIsEmpty()==1||OpStrackArray.level[OpStrackArray.top-1] { /*如果栈为空或栈顶操作符优先级小于当前操作符优先级则将其压栈*/ pushOp(op,level); } else { while(stackIsEmpty()!=1&&OpStrackArray.level[OpStrackArray.top-1]>=level) { /*操作符不断出栈并计算直到栈为空或栈顶操作符优先级大于等于当前操作符优先级*/ compute(popOp()); } pushOp(op,level);/*将当前操作符压栈*/ } } /*根据传入操作符运算，并将结果压入操作数栈*/ void compute(char op) { float tempresult;/*临时计算结果*/ float od1=popOd(); float od2=popOd();/*连续pop出两个操作数*/ switch(op)/*根据传入操作符计算*/ { case '+': tempresult=od2+od1; break; case '-': tempresult=od2-od1; break; case '*': tempresult=od2*od1; break; case '/': tempresult=od2/od1; break; } pushOd(tempresult);/*将计算结果压栈*/ } 四、运行结果 图3中缀转后缀算法运算结果 图4 一边扫描一边计算算法运算结果五、遇到的问题及解决 这部分我主要遇到了如下几个问题，其内容与解决方法如下所列： 中缀转后缀算法： ●问题1：扫描完成后输出的后缀表达式会带有’(’，从而导致计算不正确。 解决方法：在遇到’)’后，程序会调用pop方法不断从操作符栈内弹出操作符存入后 缀表达式数组，直到遇到’(’。就是在这里，在遇到’(’后应该直接弹出’(’而不应该将 其存入后缀表达式数组，改正后后缀表达式中自然就不再存在’(’。 ●问题2：虽然解决了第一个问题，但是有时后缀表达式仍然输出不正确，不是掉个 操作符就是少个数字。 解决方法：经过深入研究，我最终发现凡是当遇到’)’需要连续从操作符栈pop出操 作符时就会出现这个问题。原来输入表达式字符串和存储后缀表达式字符串的索引 相同，因为我想数字与数字之间有操作符自然分割，但是在这种情况下，输入表达 式字符串索引的确是向后推1，而存储后缀表达式字符串的索引就不止向后推1了，需要根据pop出的操作符个数来确定。因此我声明了另一个索引z，而判断操作符 入栈规则的方法也将返回pop出操作符的数量，再将z索引向后推相应的个数这个 问题就解决了。 ●问题3：当输入表达式不正确时，程序将出现不同问题。例如，’)’出现在了’(’前面， 程序将如图所示错误： 图5 问题3 而缺少’)’与’(’匹配时将不会得到正确结果。 解决方法：在遇到’)’后不断pop出操作符栈内操作符，当栈为空时还没出现’(’，则 输出“Expression is not valid!”并return主方法；另声明一个变量eq，当遇到’(’时 eq+1，遇到’)’时eq-1，扫描结束后判断eq是否为0，是则说明表达式合法，程序 继续运行，不是则说明不合法，输出“Expression is not valid!”并return主方法。 一边扫描一边计算算法： ●问题4：输入的数经转换为float型后与原来不符。 解决方法：扫描输入表达式时需要从中分离出操作数，push进数栈，而分离出来 的数字是一个字符串，要存放在一个临时字符串数组中，之后通过函数将其转换为 float型，push进数栈。就是这时再处理完一个数后，没有将临时数组清空而导致 下一次数字转换的错误。在每次处理后，将数组清空，这个问题自然也就引刃而解 啦。 六、心得体会 通过这次作业，让我对栈的原理有了更深的理解。而在作业中对栈的使用也是我体会到栈这个结构的强大之处，如果运用得当，可以使我们写的程序更加简单清晰，性能也更加优良。正是因此，让我懂得了一个好的算法，可以使平时我们看上去很难解决的问题轻而易举地得到解决。从大局上看，编写程序之前一定要先思考解决这一问题的思想，实现这项功能的算法，不能一开始就考虑细节上的问题。而编写代码时，则需要好好考虑好细节，思考各种各样情况，不能再想着整体上的实现。不然就将使自己的思维混乱，体现在程序上就是结构混乱，不仅别人很难看懂，自己也很容易被弄得云里雾里。另一方面，也让我认识到了自己的不足之处，在写代码的过程中出现一些十分弱智的错误，在调试的过程中为了寻找这些本可以避免的错误而浪费了大量时间和精力。有些看上去很容易的地方，实现起来并不是想象的那么容易，还需要下一番功夫。 竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告 篇一：数据结构实验二——算术表达式求值实验报告 《数据结构与数据库》 实验报告 实验题目算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系pb0920603 姓学 邮名：李维谷号：pb09206285箱： liwg@https://www.sodocs.net/doc/3b7373366.html,指导教师：贾伯琪 实验时间：20XX年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个(:数据结构表达式求值实验报告)算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 课程设计报告 题目：算术表达式求值 一、需求分析 1、设计要求： 给定一个算术表达式，通过程序求出最后的结果 1>、从键盘输入要求解的算术表达式； 2>、采用栈结构进行算术表达式的求解过程； 3>、能够判断算术表达式正确与否； 4>、对于错误表达式给出提示； 5>、对于正确的表达式给出最后的结果； 2、设计构想： 为了实现算符优先算法使用两个工作栈，一个称作OPTR，以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。在操作数和操作符入栈前，通过一个函数来判别，输入的是操作数还是操作符，操作数入OPND，操作符入OPTR。在输入表达式的最后输入‘#’，设定‘#’的优先级最低，代表表达式输入结束。在表达式输入过程中，遇操作数则直接入栈，遇到运算符则与栈顶运算符比较优先级,若当前运算符优先级高，则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为‘#’，运算结束。 二、概要设计 1、本程序包含的模块： （1）栈模块——实现栈抽象数据类型 （2）运算模块——实现数据表达式的运算（3）主程序模块 三、详细设计 （1）栈模块 1、定义栈结构 struct Sqstack { elemtype *top;//栈顶元素 elemtype *base; //栈底元素 int stacksize;//栈的大小 }; 2、栈的基本操作 ①初始化栈 status initstack(struct Sqstack &s) { s.base=(elemtype *)malloc(stack_size*sizeof(elemtype)); if(!s.base) return OVERFLOW; s.top=s.base; s.stacksize=stack_size; return OK; } ②入栈 status push(struct Sqstack &s,elemtype e) { 编译原理实验指导 实验安排： 上机实践按小组完成实验任务。每小组三人，分别完成TEST语言的词法分析、语法分析、语义分析和中间代码生成三个题目,语法分析部分可任意选择一种语法分析方法。先各自调试运行，然后每小组将程序连接在一起调试，构成一个相对完整的编译器。 实验报告： 上机结束后提交实验报告，报告内容： 1．小组成员； 2．个人完成的任务； 3．分析及设计的过程； 4．程序的连接； 5．设计中遇到的问题及解决方案； 6．总结。 实验一词法分析 一、实验目的 通过设计编制调试TEST语言的词法分析程序，加深对词法分析原理的理解。并掌握在对程序设计语言源程序进行扫描过程中将其分解为各类单词的词法分析方法。 编制一个读单词过程，从输入的源程序中，识别出各个具有独立意义的单词，即基本字、标识符、常数、运算符、分隔符五大类。并依次输出各个单词的内部编码及单词符号自身值。 二、实验预习提示 1．词法分析器的功能和输出格式 词法分析器的功能是输入源程序，输出单词符号。词法分析器的单词符号常常表示 成以下的二元式(单词种别码，单词符号的属性值)。 2．TEST语言的词法规则 《数据结构与数据库》 实验报告 实验题目 算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系PB0920603 姓名：李维谷 学号：PB09206285 邮箱：liwg@https://www.sodocs.net/doc/3b7373366.html, 指导教师：贾伯琪 实验时间：2010年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 输出结果：194.4 武汉工程大学计算机科学与工程学院 《编译原理》实验报告 专业班级实验地点 学生学号指导教师 学生姓名实验时间 实验项目实验二、算术表达式递归下降分析程序设计 实验类别操作性（）验证性（）设计性（√）综合性（）其它实 验目的及要求（1）掌握自上而下语法分析的要求与特点。（2）掌握递归下降语法分析的基本原理和方法。（3）掌握相应数据结构的设计方法。 成绩评定表 类别评分标准分值得分合计 上机表现积极出勤、遵守纪律 主动完成实验设计任务 30分 实验报告及时递交、填写规范 内容完整、体现收获 70分 说明： 评阅教师： 日期： 实验内容 一、实验目的 （1）掌握自上而下语法分析的要求与特点。 （2）掌握递归下降语法分析的基本原理和方法。 （3）掌握相应数据结构的设计方法。 二、实验内容 编程实现给定算术表达式的递归下降分析器。 算术表达式文法如下：E→E+T | T T→T*F | F F→(E) | i 设计说明：首先改写文法为LL(1)文法；然后为每一个非终结符，构造相应的递归函数，函数的名字表示规则左部的非终结符；函数体按规则右部符号串的顺序编写。 三、设计分析 （1）消去该文法左递归，得到文法： E→TE1 E1→+TE1|ε T→FT1 T1→*FT1|ε F→(E)| I （2）根据LL（1）文法的判断条件，计算这个文法的每个非终结符的FIRST 集和FOLLOW集，经验证，改后的文法已经是LL（1）文法。 （3）最后构造递归下降分析程序，每个函数名是相应的非终结符，函数体则是根据右部符号串的结构编写。 a.当遇到非终结符时，如：+。 则编写语句if(当读来的输入符号== +) 读下一个输入符号 b.当遇到非终结符时，例如：T。则编写语句调用T()。 c.当遇到非终结符→ε规则时，例如：T→ε。 则编写语句 if(当前读来的输入字符不属于FOLLOW(T)) error() d.当某个非终结符的规则有很多个候选式时。 按LL(1)文法的条件能唯一的选择一个候选式进行推导。 （4）递归下降分析法是确定的自上而下分析法，基本思想是，对文法中的每个非终结符编写一个函数，每个函数的功能是识别由该非终结符所表示的语法成分。因此需要分别构造E,E1,T,T1,F函数来执行自己的识别功能，根据文法的内容顺序决定函数的识别功能。Scaner函数用于字符串的推进，input函数用于字符串的输入。 软件技术基础实验报告 实验名称：表达式计算器 系别：通信工程 年级： 班级： 学生学号： 学生姓名： 《数据结构》课程设计报告 题目简易计算表达式的演示 【题目要求】 要求：实现基本表达式计算的功能 输入：数学表达式，表达式由整数和“+”、“-”、“×”、“/”、“（”、“）”组成输出：表达式的值 基本操作：键入表达式，开始计算，计算过程和结果记录在文档中 难点：括号的处理、乘除的优先级高于加减 1．前言 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/、=，用#表示结束。 算法输出：表达式运算结果。 算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。 2．概要设计 2.1 数据结构设计 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top 指示栈顶元素在顺序栈中的位置，base 为栈底指针，在顺序栈中，它始终指向栈底，即top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针top 增1，删除栈顶元素时，指针top 减1。 2.2 算法设计 为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR ，用以寄存运算符，另一个称做OPND ，用以寄存操作数或运算结果。 1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素； 2.依次读入表达式，若是操作符即进OPND 栈，若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR 栈的栈顶元素和当前读入的字符均为”#”）。 2.3 ADT 描述 ADT Stack{ 数据对象：D={ i a |i a ∈ElemSet,i=1,2,…，n, n ≧0} 数据对象：R1={< 1 ,-i i a a >| 1-i a ,D a i ∈,i=2,…，n} 计算机与信息学院 操作系统与编译原理联合课程设计报告》 专题：编译原理部分学生姓名：学号： 专业班级：指导教师： 2014 年7 月 一、设计目标设计一个语法制导翻译器，将算术表达式、for 语句、while 语句翻译成四元式。要求先确定一个定义算术表达式、for 语句、while 语句的文法，为其设计一个语法分析程序，为每条产生式配备一个语义子程序，按照一遍扫描的语法制导翻译方法，实现翻译程序。对用户输入的任意一个正确的表达式，程序将其转换成四元式输出。 二、设计思路开发平台：Visual C++ MFC 解决这个问题的方案分为以下几个步骤： 1. 将算数表达式、for 语句、while 语句转换为四元式的第一步为对读入的表达式进行处理，即删除不必要的空格、回车、换行等，保证之后的步骤能够顺利进行。 2. 分析算术表达式、for 语句、while 语句的文法。 3. 通过词法分析判断语句中的每个字符的类型，如：数字、字母、符号等。 4. 建立每种文法的LR(0) 分析表，通过每个文法的LR(0) 分析表对相应的表达式进行语法分析。 5. 在语法分析正确的情况下，通过语法分析的中间过程的符号栈输出四元式，四元式的形式为：( op arg1 arg2 result )。 (一)算术表达式转换为四元式将算术表达式转换为四元式首先考虑了括号的问题，对于不同的算术表达式第一步进行词法分析，即确定各种符号的位置。而括号中的式子是优先级最高的，应该最先进行处理。我使用了一个数组记录算术表达式中括号的位置，并且定义了first_cc 和first_jj 函数对括号内的乘除法和加减法分别进行处理。后将括号内的式子以四元式的形式输出。通过以上转换，已将原算术表达式中的括号中的内容使用大写字母' A'、' B'??等代替(其中定义声明了change 函数，用来将括号部分替换为大写字母)。新的式子中，只含有加减乘除以及赋值这四种运算，后根据优先级的不同，逐步生成四元式。 其算法流程图如右图所示。 (二)for 语句转换为四元式 1. For 语句的文法如下： S-> f ( E ; F ; G ){ H ;} S-> f ( E ; X ; Y ){ H ;} E-> id = c F-> id < c G-> id + + X-> id > c Y-> id –– 实验表达式求值问题 1.问题描述 表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3.中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀表达式（如：11 22 7 4 - * 3 / +）和前缀表达式（+ 11 / * 22 - 7 4 3）。后缀表达式 和前缀表达式中没有括号，给计算带来方便。如后缀表达式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。 2.数据结构设计 （1）顺序栈类定义：首先应在类中定义成员函数，以此来完成顺序栈的相关操作，如下： class SqStack { private: T *base; //栈底指针 int top; //栈顶 int stacksize; //栈容量public: SqStack(int m); //构建函数 ~SqStack(){delete [] base;top=0;stacksize=0;} //析构函数 void Push(T x); //入栈 T Pop(); //出栈 T GetTop(); //获取栈顶元素 int StackEmpty(); //测栈空 void ClearStack(); //清空栈 void StackTop(); //返回栈顶指针 void StackTranverse(); //显示栈中元素 }; （2）顺序栈类实现：对顺序栈进行初始化，初始化的首要操作就是创建一个空顺序栈。 Step1：申请一组连续的存空间为顺序栈使用： base=new T[m]; i f(base==NULL) { cout<<"栈创建失败，退出!"< 编译原理实验报告 题目：对下面的文法对象，使用c语言构造它的预测分析程序；并任意给一算术表达式进行分析测试． 分析对象对象定义如下： 算术表达式→项｜算术表达式+项｜算术表达式－项 项→因式｜项*因式｜项／因式 因式→变量｜（算术表达式） 变量→字母 字母→A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z 一、分析 语法分析部分我们我们采用ｌｌ（１）方法实现，采用ｌｌ（１）方法实现语法发分析要求文法满足以下要求： 一个文法能否用确定的自顶向下分析与文法中相同左部的每个产生式右部的开始符号集合有关，当有右部能=*=>ε时则与其左部非终结符的后跟符号集合也有关，此外在产生式中不存在左递归即经过压缩，无左递归，无回溯。它的基本思想是从左到右扫描源程序，同时从识别符号开始生成句子的最左推导，并只向前查看一个输入符号，便能唯一确定应选择的规则。 下面将确切地定义满足确定的自顶向下分析条件的文法即LL(1)文法及LL(1)文法的判 别并介绍如何对非LL(1)文法进行等价变换问题，也就是消除一个文法中的左递归和左公共因子。 注意： 一个文法中含有左递归和左公共因子绝对不是LL(1)文法，所以也就不可能用确定的自顶向下分析法，对此结论可以证明。然而，某些含有左递归和左公共因子的文法在通过等价变换把它们消除以后可能变为LL(1)文法，但需要用LL(1)文法的定义判别，也就是说文法中不含左递归和左公共因子，只是LL(1)文法的必要条件。 LL(1) 文法的定义（5种定义）： 一个文法符号串的开始符号集合定义如下： 定义 1.设G=(VT，VN，S，P)是上下文无关文法,α是任意的文法符号串,FIRST(α)是从α推导出的串的开始符号的终结符集合。。。。 FIRST(α)={a|α=*=>aβ,a∈VT，α,β∈V*}若α=*=>ε,则规定ε∈FIRST(α)．当一个文法中相同左部非终结符的右部存在能=*=>ε的情况则必须知道该非终结符的后跟符号的集合中是否含有其它右部开始符号集合的元素。为此，我们定义一个文法非终结符的后跟符号的集合如下： 定义2.设G=(VT，VN，S，P)是上下文无关文法，A∈VN，S是开始符号 FOLLOW(A)=｛a|S=*=>μAβ,且a∈VT，a∈FIRST(β),μ∈VT* ,β∈V+｝若S=*=>μAβ,且βε, 则#∈FOLLOW(A)。也可定义为：FOLLOW(A)={a|S=*=> …Aa…,a ∈VT} 若有S=*=> …A，则规定#∈FOLLOW(A) //代码部分： #include ElemType Pop(SqStack &s,ElemType &e) { if (s.top==0) { cout<<"Stack is empty!"< 目录 1．前言 (2) 2．问题描述 (3) 3．总体设计·····················································································错误！未定义书签。 3.1 概要设计 ······························································································错误！未定义书签。 3.1.1 数据结构的选择 (3) 3.1.2 相关功能函数 (3) 3.1.3 函数模块调用关系 (4) 3.2详细设计和编码 (5) 4．运行与测试 (9) 4.1 上机调试 (9) 4.2 算法时间和空间性能分析 (10) 4.3程序运行测试结果 (11) 5. 总结与心得 (13) 5.1设计中难点的总结以及其它解决方案 (13) 5.2 实验心得 (14) 6. 用户使用说明 (16) 7. 参考文献 (16) 8. 附录1（源代码清单） (16) 9. 附录2（成绩评定表） (25) 1 1.前言 课程设计是实践性教学中的一个重要环节，它以某一课程为基础，它可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。 在数据结构的学习和课程设计过程中，我发现它要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，都必须加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。对于我们专业来说，虽然说对技术要求不是特别高，但是在实际操作过程中，没有足够的专业知识对于编程来说是远远不可以达到要求的，所以对于这次的课程设计，我们必须要通过自己额外补充知识来完成它。 在这次的课程设计中我选择的题目是表达式的求值演示。它的基本要求是：以字符序列的形式从终端输入语法正确的，不含变量的表达式。利用算符优先关系，实现对算术四则混合运算表达式的求值，并演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。对于表示出栈在每执行一个过程中都要输出它的变化，这点我认为在编程中是比较困难的，以我自身的能力，是不可能在规定的时间内完成任务的，所以我参考了很多有价值的书籍来帮助我完成我的程序设计。 2 实验四中间代码生成 一．实验目的： 掌握中间代码的四种形式（逆波兰式、语法树、三元式、四元式）。 二．实验内容： 1、逆波兰式定义:将运算对象写在前面，而把运算符号写在后面。用这种表示法表示的表 达式也称做后缀式。 2、抽象（语法）树：运算对象作为叶子结点，运算符作为内部结点。 3、三元式：形式序号：（op,arg1,arg2） 4、四元式：形式（op,arg1,arg2,result） 三、以逆波兰式为例的实验设计思想及算法 (1)首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。 (2)读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。 (3)从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。 (4)如果不是数字，该字符则是运算符，此时需比较优先关系。 做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将此运算符栈顶的运算符从栈中弹出，将该字符入栈。 (5)重复上述操作(1)-(2)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。 四、程序代码： //这是一个由中缀式生成后缀式的程序 #include<> #include<> #include<> #include<> #define maxbuffer 64 void main() { char display_out(char out_ch[maxbuffer], char ch[32]); //int caculate_array(char out_ch[32]); static int i=0; static int j=0; char ch[maxbuffer],s[maxbuffer],out[maxbuffer]; cout<<"请输入中缀表达式: "; XXXXXX大学《数据结构》课程设计报告 班级： 学号： 姓名： 指导老师： 目录 一算术表达式求值 一、需求分析 二、程序的主要功能 三、程序运行平台 四、数据结构 五、算法及时间复杂度 六、测试用例 七、程序源代码 二感想体会与总结 算术表达式求值 一、需求分析 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 二、程序的主要功能 （1）从键盘读入一个合法的算术表达式，输出正确的结果。 （2）显示输入序列和栈的变化过程。 三、程序运行平台 Visual C++ 6.0版本 四、数据结构 本程序的数据结构为栈。 （1）运算符栈部分： struct SqStack //定义栈 { char *base; //栈底指针 char *top; //栈顶指针 int stacksize; //栈的长度 }; int InitStack (SqStack &s) //建立一个空栈S { if (!(s.base = (char *)malloc(50 * sizeof(char)))) exit(0); s.top=s.base; s.stacksize=50; return OK; } char GetTop(SqStack s,char &e) //运算符取栈顶元素 { if (s.top==s.base) //栈为空的时候返回ERROR { printf("运算符栈为空!\n"); return ERROR; } else e=*(s.top-1); //栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OK 表达式求值 一目的 利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题 目，利用C/C++语言进行程序设计，并规地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描 述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果 二需求分析 设计一个程序，演示以字符序列的形式输入不含变量的实数表达式求值的计算结果。对于这个程序我们从输入，输出，和功能三方面来分析。 1.程序输入：从键盘上输入表达式，一个算术表达式，由常量、运算符和括号组成（以字符串形式输入，不含变量）。为了简化，操作数只能为浮点数，操作符为“ +”、“-”、“*”、“/”、“（”、“）”，用“#“表示结束。 2.程序输出：表达式运算结果，运算符栈、运算数栈、输入字符和主要操作变化过程，如运算符栈、运算数栈的出入记录，字符出入栈的过程，打印出完整的过程。 3.功能要求及说明：从键盘上输入表达式。分析该表达式是否合法（包含分母不能为零的情况）： （1）是数字，则判断该数字的合法性。 （2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值。 （3）若是其它字符，则返回错误信息。 若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。 三概要设计 1.数据结构的选择： 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。 第八章习题答案 2、请将算术表达式翻-（a+b）*(c+d)+(a+b+c)翻译为：（1）四元式 （2）三元式 （3）间接三元式 答： （2）三元式 （3）间接三元式 间接码表： 三元式： 4、修改图8.5中计算声明语句中的名字的类型及相对对峙的翻译方案，以允许在一个声明中可以同时声明多个变量名。 答： 翻译方案如下： P->{ offset:= 0 } D D-> D;D D->L L->id,L1 { L.type = L1.type; L.width = L1.width; enter(id,name,L.type,offset; Offset:= offset +L.width } L->:T{ L.type = T.type; L.width = T.width;} T->integer { T.type = integer; T.width:= 4 } T->real { T.type= real; T.width:= 8 } T-> array[num] of T1 { T.type:= array(num.val, T1.type); T.width:= num.val X T1.width } T->^T1 {T.type:=pointer(T1.type); T.width : = 4 } 7、利用8.11的翻译方案，将下面的赋值语句翻译成三地址代码： A[i，j] = B[i,j] + C[A[k,l]]+D[i+j] 答： 令: 域宽为w A的维数为：da1,da2, 不变部分为na, B的维数为db1,db2, 不变部分nb C的维数为dc,不变部分nc D的维数为dd,不变部分nd, t1 := i*db1 t1:= t1+j t2:= B-nb t3:=w*t1 t4:=t2[t3] xb = t4; t1 := k*da1 t1:= t1+l t2:= A-na t3:=w*t1 t4:=t2[t3] xa = t4; t1:=xa; t2:=C-nc; t3:=w*t1 t4:=t2[t3] xca:=t4 t1:=i+j; t2:=D-nd; t3:=w*t1; t4:=t2[t3]; xd=t4; t5:=xb+xca; t6:=t5+xd; t1 := i*da1 t1:= t1+j t2:= A-na t3:=w*t1 t2[t3]:=t6 目录 1概述 (2) 1.1目的及意义 (2) 2系统分析 (2) 2.1需求分析 (2) 3概要设计 (2) 3.1系统总体结构 (2) 3.2程序算法图 (2) 4详细设计 (3) 4.1中缀表达式转换为后缀表达式 (3) 4.1.1求运算符优先级函数 (4) 4.1.2输出队列 (4) 4.2后缀表达式的求值 (4) 5运行与测试 (5) 5.1 输入表达式： (5) 5.2 输出结果： (5) 6总结和心得 (6) 6.1心得与问题 (6) 6.2总结 (6) 参考文献 (6) 1概述 1.1目的及意义 我们在很早的时候就开始学习书写及计算表达式，可以说运用起来很熟练了，但有时候并不想自己计算，交给计算器是时有的事，然而普通的计算器并不懂得优先级，给计算带来了一定的不便。 本程序实现的目的是将人们习惯的中缀表达式转换为计算机所能理解的后缀表达式以方便计算，最终得出我们所需要的正确的答案。 2系统分析 2.1需求分析 当我们需要进行一长串的计算时，各种运算符夹杂在一起，通过笔算很容易得出结果。然而计算机并没有人脑那么聪明，它并不懂得先乘除后加减，有括号要先计算括号里面的，它只知道从左到右的进行计算，这就造成了计算机计算的失误，科学的计算是人们非常需要的计算工具。 3概要设计 3.1系统总体结构 整个系统结构如图3-1-1所示，结构非常清楚，程序顺序执行，首先提示用户输入需要计算的表达式，经过转换得到后缀表达式，最后结果将数据显示到主屏幕上即可。 图3.1.1 系统总体结构图 3.2程序算法图 本程序所用的数据结构类型是栈和队列。 首先提示用户输入中缀表达式，再利用程序将中缀表达式转换为后缀表达式，其中数字入队列，算术运算符入栈。 图3.2.1 程序算法图 4详细设计 4.1中缀表达式转换为后缀表达式 将中缀表达式转换为后缀表达式首先需要扫描中缀表达式，当遇到数字时，将其入队列，当遇到运算符时，若是低优先级则直接入栈，若是高优先级则将低优先级运算符弹出，并入队列，再将此次运算符入栈，最终形成后缀表达式 图4.1.1后缀表达式的转换 其伪代码算法如下： switch(c){ case '0' to case '9' :EnQueue(Q,c) case '(': Push(S,c) case ')' to case'#': t=Pop(S); if (t!='(' && t!='#') EnQueue(Q,t); } while (t!='(' && S->top!=-1); case '+' || case '-'|| case '*'|| case '/': while (Priority(c)<=Priority(GetTop(S))) //比较优先级 EnQueue(Q, Pop(S)) Push(S,c) } 二课程设计2——算术表达式求值 一、需求分析 二、程序的主要功能 三、程序运行平台 四、数据结构 五、算法及时间复杂度 六、测试用例 七、程序源代码 三感想体会与总结 算术表达式求值 一、需求分析 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 二、程序的主要功能 （1）从键盘读入一个合法的算术表达式，输出正确的结果。 （2）显示输入序列和栈的变化过程。 三、程序运行平台 Visual C++ 6.0版本 四、数据结构 本程序的数据结构为栈。 （1）运算符栈部分： struct SqStack //定义栈 { char *base; //栈底指针 char *top; //栈顶指针 int stacksize; //栈的长度 }; int InitStack (SqStack &s) //建立一个空栈S { if (!(s.base = (char *)malloc(50 * sizeof(char)))) exit(0); s.top=s.base; s.stacksize=50; return OK; } char GetTop(SqStack s,char &e) //运算符取栈顶元素 { if (s.top==s.base) //栈为空的时候返回ERROR { printf("运算符栈为空!\n"); return ERROR; } else e=*(s.top-1); //栈不为空的时候用e做返回值，返回S的栈顶元素，并返回OK return OK; } int Push(SqStack &s,char e) //运算符入栈 { if (s.top-s.base >= s.stacksize) { printf("运算符栈满!\n"); s.base=(char*)realloc (s.base,(s.stacksize+5)*sizeof(char) ); //栈满的时候，追加5个存储空间 if(!s.base) exit (OVERFLOW); s.top=s.base+s.stacksize; s.stacksize+=5; } *(s.top)++=e; //把e入栈 return OK; } int Pop(SqStack &s,char &e) //运算符出栈 { if (s.top==s.base) //栈为空栈的时候，返回ERROR { printf("运算符栈为空!\n"); return ERROR; } else { package语法分析; public class displymain { public static void main(String args[]) { new frame(); } } package 语法分析; import java.awt.GridLayout; import java.awt.event.ActionEvent; import java.awt.event.ActionListener; import javax.swing.*; public class frame implements ActionListener{ JFrame frame1; JLabel L1,L2; JButton bt,bt2; JTextField input,result; top_down_grammar a =new top_down_grammar(); public frame() { frame1=new JFrame(""); input=new JTextField(20); result=new JTextField(20); L1=new JLabel("请输入表达式以#结束"); L2=new JLabel("结果是："); bt=new JButton("语法分析"); bt2=new JButton("关闭"); frame1.setTitle("递归下降子程序分析语法"); frame1.setLayout(new GridLayout(3,1)); frame1.add(L1); frame1.add(input); frame1.add(L2); frame1.add(result); frame1.add(bt); frame1.add(bt2); bt.addActionListener(this); bt2.addActionListener(this); frame1.setSize(500, 500); frame1.setVisible(true); } public void actionPerformed(ActionEvent e) { a.i=0; a.x.str=input.getText(); 高级语言程序设计 《算术表达式求值》 课程设计报告 算术表达式求值 系统可以实现实现对算术四则混合运算表达式求值，并打印求值过程中运算符栈、操作数栈的变化过程。 第二章系统分析 开始运行时界面如下： 你可以输入一个表达式，按E对其进行求值。 第四章系统实现 #include if(ch=='+'||ch=='-') return 2; if(ch=='*'||ch=='/') return 3; if(ch=='(') return -1; return 0; } double result(double num1,char op,double num2)//计算 { if(op=='+') return num1+num2; if(op=='-') return num1-num2; if(op=='*') return num1*num2; if(op=='/') return num1/num2; return 0; } int compute(char str[]) { double num=0; int i=0,j=1,k=1; numTop=opTop=0; while(str[i]!='\0'||opTop>0) { if(str[i]>='0'&&str[i]<='9') num=num*10+str[i]-'0'; else if( k==1&&str[i]=='-'&&(i==0||op(str[i-1])) ) k=-1; else { if(i>0&&!op(str[i-1])&&str[i]!='('&&str[i-1]!=')')数据结构表达式求值实验报告
算术表达式的求解-数据结构课程设计报告
编译原理实验指导
数据结构实验二——算术表达式求值实验报告
编译原理实验报告算术表达式递归下降分析程序设计
数据结构算术表达式求值实验报告
编译原理课程设计——算术表达式、for、while语句转换为四元式
数据结构课程设计_表达式求值问题
编译原理语法分析程序
数据结构表达式求值代码
数据结构算术表达式求值课程设计
编译原理实验 中间代码生成
数据结构课程设计_表达式求值【完整版】
数据结构课程设计：算术表达式
编译原理第八章习题答案
数据结构课程设计表达式求值问题
最新《数据结构》算术表达式求值
编译原理语法分析 算术表达式
数据结构课程设计算术表达式求值计算器.doc
相关文档
- 数据结构课程设计表达式求值【完整版】
- 数据结构表达式求值(可以求小数与多位数)
- 数据结构算术表达式求值实验报告
- 数据结构课程设计_表达式求值完整版
- 数据结构课程设计算术表达式求值计算器.doc
- 数据结构实验报告_表达式求值
- 表达式求值课程设计(数据结构C语言版)
- 数据结构表达式求值完整篇(含实验报告)
- 数据结构表达式求值代码
- 长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告
- 数据结构算术表达式求值实验报告
- 长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告
- 数据结构算术表达式求值实验报告
- 数据结构实验二——算术表达式求值实验报告
- 数据结构算术表达式求值实验报告
- 数据结构课程设计表达式求值问题
- 数据结构表达式求值完整篇(含实验报告)
- 实用数据结构基础（第二版）实验7：标识符树与表达式求值
- 数据结构表达式求值实验报告
- 表达式求值(数据结构)