如何用栈去实现表达式求值?
如何用栈去实现表达式求值?
算法已经有了,但是实现起来有困难!请各位大侠帮帮忙!
[解决办法]
#include <malloc.h>
#include <stdio.h>
#include <ctype.h> //判断是否为字符的函数的头文件
#define maxsize 100
typedef int elemtype;
typedef struct sqstack sqstack;//由于sqstack不是一个类型 而struct sqstack才是
char ch[7]={ '+ ', '- ', '* ', '/ ', '( ', ') ', '# '};//把符号转换成一个字符数组
int f1[7]={3,3,5,5,1,6,0};//栈内元素优先级
int f2[7]={2,2,4,4,6,1,0};//栈外的元素优先级
struct sqstack
{
elemtype stack[maxsize];
int top;
};
void Initstack(sqstack *s)
{
s-> top=0;
}
void Push(sqstack *s,elemtype x)
{
if(s-> top==maxsize-1)
printf( "Overflow\n ");
else
{
s-> top++;
s-> stack[s-> top]=x;
}
}
void Pop(sqstack *s,elemtype *x)
{
if(s-> top==0)
printf( "underflow\n ");
else
{
*x=s-> stack[s-> top];
s-> top--;
}
}
elemtype Gettop(sqstack s)
{
if(s.top==0)
{
printf( "underflow\n ");
return 0;
}
else
return s.stack[s.top];
}
elemtype f(char c)
{
switch(c)
{
case '+ ':
return 0;
case '- ':
return 1;
case '* ':
return 2;
case '/ ':
return 3;
case '( ':
return 4;
case ') ':
return 5;
default:
return 6;
}
}
char precede(char c1,char c2)
{
int i1=f(c1);
int i2=f(c2);//把字符变成数字
if(f1[i1]> f2[i2])//通过原来设定找到优先级
return '> ';
else if(f1[i1] <f2[i2])
return ' < ';
else
return '= ';
}
int Operate(elemtype a,elemtype theta,elemtype b)
{
int sum;
switch(theta)
{
case 0:
sum=a+b;
break;
case 1:
sum=a-b;
break;
case 2:
sum=a*b;
break;
default:
sum=a/b;
}
return sum;
}
EvaluateExpression()
{
char c;
int i=0,sum=0;
int k=1,j=1;//设置了开关变量
elemtype x,theta,a,b;
sqstack OPTR,OPND;
Initstack(&OPTR);
Push(&OPTR,f( '# '));//0压入栈
Initstack(&OPND);
c=getchar();
if(c==ch[2]||c==ch[3]||c==ch[5]||c==ch[6])//先对＋和-的情况忽略和左括号的情况
{
printf( "错误1 \n ");
k=0;
return 0;
}
if(c==ch[0])
c=getchar();//如果是＋，把它覆盖
if(c==ch[1])
{
j=0;
c=getchar();//也把－号覆盖
}
while(c!= '# '||ch[Gettop(OPTR)]!= '# ')
{
if(isdigit(c))
{
sum=0;
while(isdigit(c))
{
if(!j)
{
sum=sum*10-(c- '0 ');//实现了数字串前面有负号（之前是：sum=-(sum*10)-(c- '0 ')结果是－12＋13＝21）
}
else
sum=sum*10+(c- '0 ');
c=getchar();
}
Push(&OPND,sum);//如果还是数字先不压栈，把数字串转化成十进制数字再压栈
j=1;
}
else
if(k)
{
switch(precede(ch[Gettop(OPTR)],c))
{
case ' < ': Push(&OPTR,f(c));//把它们整型化
c=getchar();
if(c==ch[0]||c==ch[1]||c==ch[2]||c==ch[3]||c==ch[5]||c== '\n ')//要除去下个是‘（’的情况 也把以运算符归到这里来
{
printf( "出错2\n ");
k=0;
return 0;//加了开关变量和返回0的值使程序更以操作
}
break;
case '= ': Pop(&OPTR,&x);
c=getchar();
if(c==ch[0]||c==ch[1]||c==ch[2]||c==ch[3]||c==ch[5]||c== '\n ')//把ch[6]的情况也忽略了但此时并没有注意到右括号后面右运算符的情况
{
printf( "出错2\n ");
k=0;
return 0;
}
break;
case '> ': Pop(&OPTR,&theta);
Pop(&OPND,&b);
Pop(&OPND,&a);//注意这里是谁先出栈
Push(&OPND,Operate(a,theta,b));
break;
}
}
}//在这里判断是否以运算符结束是不对的
return(Gettop(OPND));
}
main()
{
int result;
printf( "输入你的算术表达式：\n ");
result=EvaluateExpression();
printf( "结果是 :%d\n ",result);
return 0;
}
[解决办法]
本计算器利用堆栈来实现。
1、定义后缀式计算器的堆栈结构
因为需要存储的单元不多，这里使用顺序栈，即用一维数组来模拟堆栈：
#define MAX 100
int stack[MAX];
int top=0;
因此程序中定义了长度为MAX的一维数组，这里MAX用宏定义为常数100，我们可以修改宏定义而重新定义堆栈的大小。
整型数据top为栈顶指示，由于程序开始时堆栈中并无任何数据元素，因此top被初始化为0。
2、存储后缀式计算器的运算数
我们定义了堆栈stack[MAX]后，就可以利用入栈操作存储先后输入的两个运算数。
下面看一下是如何实现的：
int push(int i) /*存储运算数，入栈操作*/
{
if(top <MAX)
{
stack[++top]=i; /*堆栈仍有空间，栈顶指示上移一个位置*/
return 0;
}
else /*堆栈已满，给出错误信息，返回出错指示*/
{
printf( "The stack is full ");
return ERR;
}
}
我们在调用函数push时，如果它的返回值为0，说明入栈操作成功；否则，若返回值为ERR(在程序中说明为-1)，说明入栈操作失败。
3、从堆栈中取出运算数
当程序中读完了四则运算符后，我们就可以从堆栈中取出已经存入的两个运算数，构成表达式，计算出结果。取出运算数的函数采用的正是出栈算法。在本例中，实现该算法的函数 为pop():
int pop(); /*取出运算数，出栈操作*/
{
int var; /*定义待返回的栈顶元素*/
if(top!=NULL) /*堆栈中仍有数据元素*/
{
var=stack[top--]; /*堆栈指示下移一个位置*/
return var;
}
else /*堆栈为空，给出错误信息，并返回出错返回值*/
printf( "The stack is cmpty!\n ");
return ERR;
}
同样，如果堆栈不为空，pop()函数返回堆栈顶端的数据元素，否则，给出栈空提示，并返回错误返回值ERR。
4、设计完整的后缀式计算器
有了堆栈存储运算数，后缀式计算器的设计就很简单了。程序首先提示用户输入第一个运算数，调用push()函数存入堆栈中；而后提示用户输入第二个运算数，同样调用push()函数存入堆栈中。接下来，程序提示用户输入+,-,*,/四种运算符的一种，程序通过switch_case结构判断输入运算符的种类，转而执行不同的处理代码。以除法为例，说明程序的执行流程：
case '/ ':
b=pop();
a=pop();
c=a/b;
printf( "\n\nThe result is %d\n ",c);
printf( "\n ");
break;
程序判断用户输入的是除号后，就执行上述代码。首先接连两次调用pop()函数从堆栈中读出先前输入的运算数，存入整型数a和b中；然后执行除法运算，结果存入单元c中。这时需要考虑究竟谁是被除数，谁是除数。由于开始我们先将被除数入栈，根据堆栈“先进后出”的原则，被除数应该是第二次调用pop()函数得到的返回值。而除数则是第一次调用pop()函数得到的返回值。
最后程序打印出运算结果，并示提示用户是否继续运行程序：
printf( "\t Continue?(y/n): ");
l=getche();
if(l== 'n ')
exit(0);
如果用户回答是 "n "，那么结束程序，否则继续循环。
完整的程序代码如下：
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define ERR -1
#define MAX 100 /*定义堆栈的大小*/
int stack[MAX]; /*用一维数组定义堆栈*/
int top=0; /*定义堆栈指示*/
int push(int i) /*存储运算数,入栈操作*/
{
if(top <MAX)
{
stack[++top]=i; /*堆栈仍有空间，栈顶指示上移一个位置*/
return 0;
}
else
{
printf( "The stack is full ");
return ERR;
}
}
int pop() /*取出运算数，出栈操作*/
{
int var; /*定义待返回的栈顶元素*/
if(top!=NULL) /*堆栈中仍有元素*/
{
var=stack[top--]; /*堆栈指示下移一个位置*/
return var; /*返回栈顶元素*/
}
else
printf( "The stack is empty!\n ");
return ERR;
}
void main()
{
int m,n;
char l;
int a,b,c;
int k;
do{
printf( "\tAriothmatic Operate simulator\n "); /*给出提示信息*/
printf( "\n\tPlease input first number: "); /*输入第一个运算数*/
scanf( "%d ",&m);
push(m); /*第一个运算数入栈*/
printf( "\n\tPlease input second number: "); /*输入第二个运算数*/
scanf( "%d ",&n);
push(n); /*第二个运算数入栈*/
printf( "\n\tChoose operator(+/-/*//): ");
l=getche(); /*输入运算符*/
switch(l) /*判断运算符，转而执行相应代码*/
{
case '+ ':
b=pop();
a=pop();
c=a+b;
printf( "\n\n\tThe result is %d\n ",c);
printf( "\n ");
break;
case '- ':
b=pop();
a=pop();
c=a-b;
printf( "\n\n\tThe result is %d\n ",c);
printf( "\n ");
break;
case '* ':
b=pop();
a=pop();
c=a*b;
printf( "\n\n\tThe result is %d\n ",c);
printf( "\n ");
break;
case '/ ':
b=pop();
a=pop();
c=a/b;
printf( "\n\n\tThe result is %d\n ",c);
printf( "\n ");
break;
}
printf( "\tContinue?(y/n): "); /*提示用户是否结束程序*/
l=getche();
if(l== 'n ')
exit(0);
}while(1);
}
