数据结构栈和队列作业.doc

熟练掌握栈和队列的存储结构设计及基本操作的实现；学会分析实际问题中具有栈特点的数据结构；了解表达式的前缀、中缀、后缀等计算机内表示形式。。 2. 实验内容与要求：

按常规形式输入算术表达式（例如：输入2*(6-4)+8/4），要求能够： （1）生成表达式的后缀表示，并输出； （2）生成表达式的前缀表示，并输出；

（3）基于表达式的后缀表示，对该表达式求值； （4）编写一个主程序对表达式求值函数进行测试。 3. 数据结构设计： 逻辑结构：线性结构 存储结构：顺序存储结构 4. 算法设计： #include #include #define MaxSize 100 #define Maxop 7 //定义栈 typedef struct {

char data[MaxSize]; int top; }SeqStack;

//构造运算符优先级的表格 struct {

char ch;

int pri; }

lpri[]={ {'(',1},{'*',5},{'/',5},{'+',3},{'-',3},{')',6},{'#',-1} },

rpri[]={ {'(',6},{'*',4},{'/',4},{'+',2},{'-',2},{')',1}};

//查找左边运算符的优先级 int leftpri(char op) { int i;

for (i = 0 ; i < Maxop ; i++) if (lpri[i].ch == op )

return lpri[i].pri;

}

//查找右边运算符的优先级 int rightpri(char op)

{ int i;

for (i = 0 ; i < Maxop-1 ; i++) if (rpri[i].ch == op )

return rpri[i].pri;

}

//判断是否为运算符

int InOp(char ch) { if (ch == '(' || ch == ')' || ch == '+' || ch == '-' || ch == '*' || ch == '/' ) return 1;

else

return 0;

}

//比较左右运算符大小的函数 int Precede(char op1,char op2) { if( leftpri(op1) == rightpri(op2) ) return 0; else if( leftpri(op1)else

return 1; }

//将中序表达式转换为后续表达式的函数 void trans( char *exp,char postexp[] ) { //这里定义的是存放运算符的栈

struct

{

char data[MaxSize]; int top; }op;

//初始化存放运算符的栈 int i = 0; op.top = -1; op.top++;

op.data[op.top] = '#'; //开始进行转换 while(*exp != '\\0') { //如果不是运算符 if( !InOp(*exp) ) {

//只要是0~9，就一直循环将

数字移动到 //postexp[]中

while( *exp >= '0' && *exp <=

'9') {

postexp[i++] = *exp; exp++; }

//为了区分超过9的数字 //使用#作为分隔符

postexp[i++] = '#';

}

//如果是运算符

else //比较栈内的运算符和表达式中的运算符 switch( Precede(op.data[op.top],*exp) ) { //如果栈中小运算符入栈 case -1: op.top++;

op.data[op.top] = *exp;

exp++;

break;

//如果是括号就相消 case 0:

op.top--;

exp++;

break;

//如果栈中大运算符就出栈放到 //postexp[]中 case 1:

postexp[i++] = op.data[op.top]; op.top--;

break;

} }

//当表达式遍历后将符号栈中的一切 //放到postexp[]中

while( op.data[op.top] != '#' ) { postexp[i++] = op.data[op.top]; op.top--;

}

postexp[i] = '\\0';

}

//以下几个函数来自栈的基本操作 void PUSH(SeqStack *s,char x) { s->top++; s->data[s->top]=x ;

}

int Sempty(SeqStack *s) {

if (s->top == -1) return 1;

else return 0; }

char POP(SeqStack *s) {

s->top--;

return s->data[s->top+1]; }

void SETNULL(SeqStack *s) {

s->top = -1; }

//这个是转换函数,用于谦虚表达式 void reverse(char exp[],char demoexp[]) { void PUSH(SeqStack *s,char x); int Sempty(SeqStack *s); char POP(SeqStack *s); void SETNULL(SeqStack *s); int Sempty(SeqStack *s); //这里有点乱解释下 //s是存放数据的栈,这样为了 //避免超过9的数在运算的时候乱掉 //sp是存放整个表达式的栈 //最后将整个表达式逆置 SeqStack *s,*sp; int strling,i,j;

j = strlen(exp);

s = (SeqStack

*)malloc(20*sizeof(SeqStack) ); sp = (SeqStack *)malloc(50*sizeof(SeqStack) ); SETNULL(s);

SETNULL(sp);

strling = strlen(exp) - 1; for(i = 0 ; i < j ; ) { //如果是数字的话先入s栈

if(exp[i] >='0' && exp[i] <='9') {

while(exp[i] >='0' && exp[i] <='9') {

PUSH(s,exp[i]);

i++; }

//如果扫描下一个字符不是数字了,就 //将数字全部放到sp栈中 while( !Sempty(s) ) { PUSH( sp, POP(s) );

}

}

//如果不是数字的话直接放到sp栈中

else { PUSH(sp , exp[i]); i++;

}

}

i = 0;

//退栈放到demoexp[]中 while(!Sempty(sp)) { demoexp[i] = POP(sp);

i++;

}

demoexp[i] = '\\0';

//逆置之后将括号改回来 for(i = 0 ; i < j ; i ++) { if(demoexp[i] == ')') demoexp[i] = '('; else if(demoexp[i] == '(')

demoexp[i] = ')';

} demoexp[j] = '\\0'; }

//利用后序表达式求解的函数 float compvalue(char *postexp) { //定义数据栈 struct { float data[MaxSize];

int top;

}st;

float a,b,c,d;

st.top = -1;

//如果后序表达式没结束 while( *postexp != '\\0' ) { switch( *postexp ) {

//如果是加,取数据栈中的两个数 //进行运算再放回去,下同

case '+':

a = st.data[st.top]; st.top--;

b = st.data[st.top]; st.top--; c = a + b; st.top++;

st.data[st.top] = c;

break; case '-': a = st.data[st.top]; st.top--;

b = st.data[st.top]; st.top--; c = b - a; st.top++;

st.data[st.top] = c;

break; case '*': a = st.data[st.top]; st.top--;

b = st.data[st.top]; st.top--; c = b * a; st.top++;

st.data[st.top] = c;

break; case '/': a = st.data[st.top]; st.top--;

b = st.data[st.top]; st.top--; if( a != 0 ) { c = b / a; st.top++;

st.data[st.top] = c;

}

//除零错误 else {

printf( \"\\noverflow\\n\" ); exit(0); }

break; //#就直接忽略

case '#': break;

//如果是数字的话,字符转数字然后放到数据栈中

default: d = 0;

while(*postexp >= '0' && *postexp <= '9')

{

d = 10 *d + *postexp - '0';

postexp++;

}

st.top++; st.data[st.top] = d; break; }

postexp++;

}

return (st.data[st.top]); }

//这个是去掉表达式中的\"#\"

void convert(char *postexp,char *postexptail) { int i=0,j=0;

while(postexp[i] != '\\0') { if(postexp[i] != '#') { postexptail[j] = postexp[i]; i++;

j++;

}

else i++;

}

postexptail[j] = '\\0';

}

void main() { int i;

char exp[MaxSize];

char postexptail[MaxSize]; char postexp[MaxSize]; char preexp[MaxSize]; char demoexp[MaxSize];

printf(\"请选择运算数是否大于9\\n\"); printf(\"1.不大于9\\n\"); printf(\"2.大于9\\n\"); do {

scanf(\"%d\if(i > 2 || i < 1 ) printf(\"输入错误,请重新输入

式%s\\n\

break;

} //这里解释下,在进行了多次试验发现前序表达式

//可以通过逆置中序表达式然后再进行后序转化

//然后再逆置一次就可以得到前序表达式

switch(i) {

case 1:

reverse(exp,demoexp); trans(demoexp,preexp);

\\n\");

}while(i > 2 || i < 1);

getchar(); printf(\"请输入中序表达式，以回车键结束\\n\");

gets(exp);

trans(exp,postexp);

printf(\"中序表达式%s\\n\

reverse(preexp,demoexp); convert(demoexp,preexp); printf(\"前序表达式%s\\n\

break;

reverse(exp,demoexp); case 2:

switch(i) {

case 1:

trans(demoexp,preexp); reverse(preexp,demoexp); printf(\"前序表达式%s\\n\

}

break;

convert(postexp,postexptail); printf(\"后序表达式%s\\n\ 5.

break; case 2: printf(\"后序表达实验结果：

printf(\"所求值

为%g\\n\ }

getchar();