C语言版数据结构课程设计利用栈求表达式的值

Question

编写程序实现表达式求职，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。
主要功能叙述如下：
1.从键盘上输入表达式。
2.分析该表达式是否合法
（1）是数字，则判断该数字的合法性，若合法，则压入数据到堆栈中
（2）是规定的运算符，则根据规则进行处理。在处理过程中计算该表达式的值。
（3）若是其他字符，则返回错误信息
3.若上述处理没有发现错误，则认为该表达式合法。
程序应包括以下几个功能函数
void initstack();初始化堆栈
int Make_str();语法检查并计算
int push_operate(int operate):将操作码压入堆栈
int push_num(double num):将操作数压入堆栈
int procede(int operate):处理操作码
int change_opnd(int operate):将字符型操作码转换成优先级
int push_opnd(int operate):将操作码压入堆栈
int pop_opnd();将操作码弹出堆栈
int caculate(interru_opnd):简单计算 +，-，*，/
double pop_num():弹出操作数

Answer 1

跟你的要求符合
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define MAXLEN 100
typedef struct
{
char op;
int level;
}opt;
typedef struct //定义操作符栈
{
opt st[MAXLEN];
int top;

}op_stack;

typedef struct //定义值栈
{
double D[MAXLEN];
int top;
}D_stack;
//--------对栈操作的定义-------------
opt peek(op_stack *s) //定义看栈顶函数
{
opt error=;
if(s->top>=0)
return s->st[s->top];
else
return error;
}
int IsEmpty(op_stack *s) //定义判断栈空的函数
{

if(s->top<0)
return 0;
else
return s->st[s->top].op;
}

char push(op_stack *s,opt c) //定义入栈函数
{
s->top++;
s->st[s->top]=c;
return c.op;
}

opt pop(op_stack *s) //定义出栈函数
{
opt i;
opt error=;
if(s->top>=0)
{
i=s->st[s->top];
s->st[s->top].op='\0';
s->top--;
return i;
}
else
return error;
}

void clear(op_stack *s) //定义初始化栈
{
s->top=-1;
}
//-----------------------------define the value stack-----------------------
double Dpeek(D_stack *s) //定义看栈顶函数
{
if(s->top>=0)
return s->D[s->top];
else
return 0;
}
int DIsEmpty(D_stack *s) //定义判断栈空的函数
{

if(s->top<0)
return 0;
else
return (int)(s->D[s->top]);
}

double Dpush(D_stack *s,double c) //定义入栈函数
{
s->top++;
s->D[s->top]=c;
return c;
}
double Dpop(D_stack *s) //定义出栈函数
{
double i;
if(s->top>=0)
{
i=s->D[s->top];
s->D[s->top]='\0';
s->top--;
return i;
}
else return 0;
}

void Dclear(D_stack *s) //定义初始化栈
{
s->top=-1;
}

double calval(char *exp)
{
op_stack os; //定义两个栈
D_stack ds;
char tmp[MAXLEN]=;
int i=0,leng;
double dtmp,dpoptmp;

opt A=;
opt R=;
opt M=;
opt D=;
opt B=;
opt Mo=;

clear(&os);
Dclear(&ds);

//-----定义初始化结束-----
while(*exp!='\0')
{

while(*exp >= '0' && *exp <= '9' || *exp == '.')
{
while(*exp >= '0' && *exp <= '9' || *exp == '.')
{
tmp[i++]=*exp++;
}

dtmp=atof(tmp);
Dpush(&ds,dtmp);
leng=strlen(tmp);
for(i=0;i<leng;i++)
{
tmp[i]='\0';
}
i=0;
}
//-------------------------------

switch(*exp)
{
case '+' :
if(!IsEmpty(&os) || peek(&os).level < A.level)
{
push(&os,A);
*exp++;
}
else
{
while(IsEmpty(&os) && peek(&os).level>=A.level)
{
switch(pop(&os).op)
{
case '%':
dpoptmp=Dpop(&ds);
dpoptmp=(float)((int)Dpop(&ds)%(int)dpoptmp);
Dpush(&ds,dpoptmp);
break;

case '*' :
dpoptmp=Dpop(&ds)*Dpop(&ds);
Dpush(&ds,dpoptmp);
break;
case '/' :
dpoptmp=Dpop(&ds);
dpoptmp=Dpop(&ds)/dpoptmp;
Dpush(&ds,dpoptmp);
break;
case '+':
dpoptmp=Dpop(&ds)+Dpop(&ds);
Dpush(&ds,dpoptmp);
break;
case '-':
dpoptmp=Dpop(&ds);
dpoptmp=Dpop(&ds)-dpoptmp;
Dpush(&ds,dpoptmp);
break;
}
}
push(&os,A);
*exp++;
}
break;
case '-':
if(!IsEmpty(&os) || peek(&os).level < R.level)
{
push(&os,R);
*exp++;
}
else
{
while(IsEmpty(&os) && peek(&os).level>=R.level)
{
switch(pop(&os).op)
{
case '%' :
dpoptmp=Dpop(&ds);
dpoptmp=(float)((int)Dpop(&ds)%(int)dpoptmp);
Dpush(&ds,dpoptmp);
break;

case '*' :
dpoptmp=Dpop(&ds)*Dpop(&ds);
Dpush(&ds,dpoptmp);
break;
case '/' :
dpoptmp=Dpop(&ds);
dpoptmp=Dpop(&ds)/dpoptmp;
Dpush(&ds,dpoptmp);
break;
case '+':
dpoptmp=Dpop(&ds)+Dpop(&ds);
Dpush(&ds,dpoptmp);
break;
case '-':
dpoptmp=Dpop(&ds);
dpoptmp=Dpop(&ds)-dpoptmp;
Dpush(&ds,dpoptmp);
break;
}
}
push(&os,R);
*exp++;
}
break;

case '*':
if(!IsEmpty(&os) || peek(&os).level < M.level)
{
push(&os,M);
*exp++;
}
else
{
while(IsEmpty(&os) && peek(&os).level>=M.level)
{
switch(pop(&os).op)
{
case '%' :
dpoptmp=Dpop(&ds);
dpoptmp=(float)((int)Dpop(&ds)%(int)dpoptmp);
Dpush(&ds,dpoptmp);
break;

case '*' :
dpoptmp=Dpop(&ds)*Dpop(&ds);
Dpush(&ds,dpoptmp);
break;
case '/' :
dpoptmp=Dpop(&ds);
dpoptmp=Dpop(&ds)/dpoptmp;
Dpush(&ds,dpoptmp);
break;
}
}
push(&os,M);
*exp++;
}
break;
case '/':
if(!IsEmpty(&os) || peek(&os).level < D.level)
{
push(&os,D);
*exp++;
}
else
{
while(IsEmpty(&os) && peek(&os).level>=D.level)
{
switch(pop(&os).op)
{
case '%' :
dpoptmp=Dpop(&ds);
dpoptmp=(float)((int)Dpop(&ds)%(int)dpoptmp);
Dpush(&ds,dpoptmp);
break;
case '*' :
dpoptmp=Dpop(&ds)*Dpop(&ds);
Dpush(&ds,dpoptmp);
break;
case '/' :
dpoptmp=Dpop(&ds);
dpoptmp=Dpop(&ds)/dpoptmp;
Dpush(&ds,dpoptmp);
break;
}
}
push(&os,D);
*exp++;
}
break;
case '%':
if(!IsEmpty(&os) || peek(&os).level < Mo.level)
{
push(&os,Mo);
*exp++;
}
else
{
while(IsEmpty(&os) && peek(&os).level>=Mo.level)
{
switch(pop(&os).op)
{
case '%' :
dpoptmp=Dpop(&ds);
dpoptmp=(float)((int)Dpop(&ds)%(int)dpoptmp);
Dpush(&ds,dpoptmp);
break;
case '*' :
dpoptmp=Dpop(&ds)*Dpop(&ds);
Dpush(&ds,dpoptmp);
break;
case '/' :
dpoptmp=Dpop(&ds);
dpoptmp=Dpop(&ds)/dpoptmp;
Dpush(&ds,dpoptmp);
break;
}
}
push(&os,Mo);
*exp++;
}
break;
case '(':
push(&os,B);
exp++;
break;

case ')':
while(peek(&os).level!=-2)
{
switch(pop(&os).op)
{
case '%' :
dpoptmp=Dpop(&ds);
dpoptmp=(float)((int)Dpop(&ds)%(int)dpoptmp);
Dpush(&ds,dpoptmp);
break;

case '*' :
dpoptmp=Dpop(&ds)*Dpop(&ds);
Dpush(&ds,dpoptmp);
break;
case '/' :
dpoptmp=Dpop(&ds);
dpoptmp=Dpop(&ds)/dpoptmp;
Dpush(&ds,dpoptmp);
break;
case '+':
dpoptmp=Dpop(&ds)+Dpop(&ds);
Dpush(&ds,dpoptmp);
break;
case '-':
dpoptmp=Dpop(&ds);
dpoptmp=Dpop(&ds)-dpoptmp;
Dpush(&ds,dpoptmp);
break;
}
}
pop(&os); //弹出 (
exp++;
break;
}
}
while(IsEmpty(&os))
{
switch(pop(&os).op)
{
case '%' :
dpoptmp=Dpop(&ds);
dpoptmp=(float)((int)Dpop(&ds)%(int)dpoptmp);
Dpush(&ds,dpoptmp);
break;

case '*' :
dpoptmp=Dpop(&ds)*Dpop(&ds);
Dpush(&ds,dpoptmp);
break;
case '/' :
dpoptmp=Dpop(&ds);
dpoptmp=Dpop(&ds)/dpoptmp;
Dpush(&ds,dpoptmp);
break;
case '+':
dpoptmp=Dpop(&ds)+Dpop(&ds);
Dpush(&ds,dpoptmp);
break;
case '-':
dpoptmp=Dpop(&ds);
dpoptmp=Dpop(&ds)-dpoptmp;
Dpush(&ds,dpoptmp);
break;
}

}

return Dpop(&ds);
}

void main()
{
char string[MAXLEN];
char *p=string;
printf("输入表达式:\n");
gets(p);
printf("%s=%f\n\n",string,calval(p));
}