《算术表达式求值(c++)数据结构实验》由会员分享，可在线阅读，更多相关《算术表达式求值(c++)数据结构实验（2页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验名称： 实验2 栈和队列及其应用实验目的：通过上机实验，加深理解栈和队列的特性；能根据实际问题的需要灵活运用栈和队列；掌握栈和队列的应用。实验内容：（2选1）内容1：算术表达式求值问题；内容2：航空客运订票系统。实验要求：1）在C+系统中编程实现；2）至少实现两种以上操作算法；3）写出算法设计的基本原理或画出流程图；4）算法实现代码简洁明了；关键语句要有注释；5）给出调试和测试结果；6）完成实验报告。 实验步骤: (1)算法设计为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。1.首先置操作数栈为空栈，
2、表达式起始符”#”为运算符栈的栈底元素；2.依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为”#”）。(2)算法实现typedef struct int stacksize; char *base; char *top; Stack;typedef struct int stacksize; int *base; int *top; Stack2;int InitStack(Stack *s) /构造运算符栈 s-base=(char *)malloc(STACK_INIT
3、_SIZE*sizeof(char); if(!s-base) return ERROR; s-top=s-base; s-stacksize=STACK_INIT_SIZE;return OK; int InitStack2(Stack2 *s) /构造操作数栈 s-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!s-base) return ERROR; s-stacksize=STACK_INIT_SIZE; s-top=s-base; return OK; int In(char ch) /判断字符是否是运算符，运算符即返回1 r
4、eturn(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#); int Push(Stack *s,char ch) /运算符栈插入ch为新的栈顶元素 *s-top=ch; s-top+; return 0; int Push2(Stack2 *s,int ch)/操作数栈插入ch为新的栈顶元素 *s-top=ch; s-top+; return 0; char Pop(Stack *s) /删除运算符栈s的栈顶元素，用p返回其值 char p;s-top-; p=*s-top; return p; int Pop2(Stack2 *s) /删除操作数栈s的栈顶元素，用p
5、返回其值 int p;s-top-; p=*s-top; return p;char GetTop(Stack s) /用p返回运算符栈s的栈顶元素 char p=*(s.top-1); return p; int GetTop2(Stack2 s) /用p返回操作数栈s的栈顶元素 int p=*(s.top-1); return p; char Precede(char c1,char c2) int i=0,j=0; static char array49=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !,
6、, , , , , , , !, =; switch(c1) case + : i=0;break;case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( : i=4;break; case ) : i=5;break; case # : i=6;break; switch(c2) case + : j=0;break; case - : j=1;break; case * : j=2;break; case / : j=3;break; case ( : j=4;break; case ) : j=5;break;
7、 case # : j=6;break; return (array7*i+j); int Operate(int a,char op,int b) switch(op) case + : return (a+b);case - : return (a-b); case * : return (a*b);case / : return (a/b); return 0; int num(int n) /返回操作数的长度 char p10;itoa(n,p,10); /把整型转换成字符串型n=strlen(p);return n;int EvalExpr() char c,theta,x; int
8、 n,m;int a,b; c = *ptr+; while(c!=#|GetTop(OPTR)!=#) if(!In(c)if(!In(*(ptr-1)ptr=ptr-1;m=atoi(ptr); /取字符串前面的数字段n=num(m); Push2(&OPND,m); ptr=ptr+n;c=*ptr+; else switch(Precede(GetTop(OPTR),c) case : theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b);break; return GetTop2(OPND); 实验结果:
