逆波兰表达式求值
一个用逆波兰法求包含非负实数表达式，并输出逆波兰表达式的程序//////////////////////////////////////////////
///求包含非负实数的运算表达式的值////////////
///并输出逆波兰表达式///////////////////////
///////////////////////////////////////////
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<math.h>
#define STACK_INIT_SIZE 20//存储空间初始分配量
#define STACKINCREMENT 10//存储空间分配增量
typedef float SElemType;
typedef struct sqstack
{
SElemType *base;
SElemType *top;
int stacksize;
}*SqStack;
void InitStack(SqStack s)//构造栈
{
s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!s->base)
{
printf("OVERFLOW!!");
exit(1);
}
s->top=s->base;
s->stacksize=STACK_INIT_SIZE;
}
void GetTop(SqStack s,SElemType *e)//读取栈顶元素
{
if(s->top==s->base)
{
printf("The Stack Is Empty!!\n");
exit(1);
}
*e=*(s->top-1);
}
void Push(SqStack s,SElemType e)//插入新元素
{
if(s->top-s->base>=s->stacksize)
{
s->base=(SElemType *)realloc(s->base,(s-
>stacksize+STACKINCREMENT)*sizeof(SElemType));
//增大栈空间
if(!s->base)
{
printf("The Stack Is Empty!!\n");
exit(1);
}
s->top=s->base+s->stacksize;
s->stacksize+=STACKINCREMENT;
}
*(s->top)=e;
s->top++;
}
void Pop(SqStack s,SElemType *e)//删除栈顶元素
{
if(s->top==s->base)
{
printf("The Stack Is Empty!!\n");
exit(1);
}
*e=*(--s->top);
}
int In(char e)//判断是否为7种运算符之一
{
switch(e)
{
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
case '#':return(1);break;//是运算符返回 1，否则，返回 0
default:return(0);
}
}
char Precede(char p,char c)//比较OPTR栈顶元素与取得元素的优先级
{ //栈顶元素优先级高，返回 '>'，反之返回 '<'
switch(p)
{
case '+':
case '-':
switch(c)
{
case '*':
case '/':
case '(':return '<';break;
default:return '>';break;
}
break;
case '*':
case '/':
switch(c)
{
case '(':return '<';break;
default:return '>';break;
}
break;
case '(':
switch(c)
{
case ')':return '=';break;
case '#':printf("ERROR!!\n");exit(1);
default:return '<';break;
}
break;
case ')':
switch(c)
{
case '(':printf("ERROR!!\n");exit(1);
default:return '>';break;
}
break;
case '#':
switch(c)
{
case ')':printf("ERROR!!\n");exit(1);
case '#':return '=';break;
default:return '<';break;
}
break;
}
}
SElemType Operate(SElemType x,char n,SElemType y)//四则运算
{
SElemType e;
switch(n)
{
case '+':e=x+y;break;
case '-':e=x-y;break;
case '*':e=x*y;break;
case '/':
if(y==0)//分母不能为 0
{
printf("The Denominator MUST NOT BE ZERO!!!\n");
exit(1);
}
else
{
e=x/y;
break;
}
}
return e;
}
void main()
{
SqStack OPTR,OPND;//定义运算符存储栈OPTR，数据存储栈OPND
SElemType p,s,a,b,theta;
char c,*str;//str存储逆波兰表达式
int flag,decimal_place,strsize=STACK_INIT_SIZE,num=0,i=0;//flag记录运算
数是否为小数(是=1,否=0)
//decimal_place记录运算数的小数位数
//strsize记录
str的大小
OPTR=(SqStack)malloc(sizeof(SqStack));//分配空间
OPND=(SqStack)malloc(sizeof(SqStack));
str=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
printf("Please Input The Expression Ending With '#'\n(Only including +
-*/ and non-negative Real Numbers):\n");
InitStack(OPTR);//创建运算符存储栈
Push(OPTR,'#');
InitStack(OPND);//创建数据存储栈
c=getchar();
GetTop(OPTR,&p);//p为栈顶元素
while(c!='#'||p!='#')
{
if(!In(c))//不是运算符，存入数据栈
{
if(num>=strsize)//为str增加空间
{
str=(char *)realloc(str,
(strsize+STACKINCREMENT)*sizeof(char));
strsize=strsize+STACKINCREMENT;
}
str[num++]=c;
flag=0;
decimal_place=0;
s=c-48;//字符与数字转换
c=getchar();
while(c>='0'&&c<='9'||c=='.')
{
if(num>=strsize)
{
str=(char *)realloc(str,
(strsize+STACKINCREMENT)*sizeof(char));
strsize=strsize+STACKINCREMENT;
}
str[num++]=c;
if(c=='.')
{
flag=1;
c=getchar();
continue;
}
if(flag==1)decimal_place++;
s=s*10+(c-48);
c=getchar();
}
if(num>=strsize)
{
str=(char *)realloc(str,
(strsize+STACKINCREMENT)*sizeof(char));
strsize=strsize+STACKINCREMENT;
}
str[num++]='#';
s=s/pow(10,decimal_place);
Push(OPND,s);
}
else
{
switch(Precede(p,c))
{
case '<':Push(OPTR,c);//栈顶元素优先级低，将c存入栈
c=getchar();break;
case '=':Pop(OPTR,&s);//两者优先级相同，脱去括号
c=getchar();break;
case '>':Pop(OPTR,&theta);//栈顶元素优先级高，取出OPTR中
运算符theta，取出OPND中两数据a,b，用c运算，将结果存入OPND
Pop(OPND,&b);Pop(OPND,&a);
Push(OPND,Operate(a,theta,b));
if(num>=strsize)
{
str=(char *)realloc(str,
(strsize+STACKINCREMENT)*sizeof(char));
strsize=strsize+STACKINCREMENT;
}
str[num++]=theta;
str[num++]='#';
break;
}
GetTop(OPTR,&p);
}
}//while
printf("\n");
printf("The Reverse Polish Notation is:\n");
while(i<num)//输出逆波兰表达式
{
if(str[i]=='#')printf(" ");
else printf("%c",str[i]);
i++;
}
printf("\n\n");
GetTop(OPND,&p);
printf("Answer is:%f\n",p);
}
欢迎大家指正！！
逆波兰表达式求值.pdf