算术表达式求值(c++)数据结构实验.pdf

数据结构实验报告

实验名称 ： 实验 2 栈和队列及其应用

实验目的 ：通过上机实验，加深理解栈和队列的特性；能根据实际问题的需要灵活运用栈和队列；

掌握栈和队列的应用。

实验内容 ：（2 选 1）内容 1：算术表达式求值问题；内容 2：航空客运订票系统。

实验要求： 1）在 C++系统中编程实现； 2）至少实现两种以上操作算法； 3）写出算法设计的基本原

理或画出流程图； 4）算法实现代码简洁明了；关键语句要有注释； 5）给出调试和测试

结果； 6）完成实验报告。

实验步骤 :

为” #”）。

(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_SIZE*sizeof(char));

if(!s->base) return ERROR;

s->top=s->base;

s->stacksize=STACK_INIT_SIZE;

return OK; }

int In(char ch) // 判断字符是否是运算符，运算符即返回 1

{ return(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 返回其值