更新时间：2015-12-23 22:44:36浏览次数：1+次
逆波兰表达式，它的语法规定，表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。这个知识点在数据结构和编译原理这两门课程中都有介绍，下面是一些例子：
逆波兰表达式的用途
它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下： 按顺序扫描逆波兰表达式，如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元
素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
后缀表达式求值算法:
（1）从左往右顺序扫描后缀表达式；
（2）遇到操作数就进栈；
（3）遇到操作符就从栈中弹出两个操作数，执行该操
作符规定的运算；并将结果进栈；
（4）重复上述操作，直到表达式结束。弹出栈顶元素即
为结果。
代码实现（主要是建立栈的么让偶进行出栈入栈操作）：
#include <stdio.h>
#include <malloc.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
#define M 40
/*定义堆栈*/
typedef struct{
double data[M];
int top;
}Stack;
/*初始化堆栈*/
InitStack(Stack *s)
{
s->top=0;
}
/*判断栈是否为空*/
int StEmpty(Stack *s)
{
if(s->top==0)
{
return 1;
}
else
{
return 0;
}
}
/*入栈操作*/
StPush(Stack *s,double x)
{
if(s->top==M)
{
printf("The stack is overflow!");
}
else
{
s->top=s->top+1;
s->data[s->top]=x;
}
}
/*出栈操作*/
double StPop(Stack *s)
{
double t;
if(!StEmpty(s))
{
t=s->data[s->top];
s->top=s->top-1;
}
else
{
printf("StPop:The stack is empty!");
t=NULL;
}
return t;
}
/*获取栈顶元素*/
double StGetTop(Stack *s)
{
double t;
if(!StEmpty(s))
{
t=s->data[s->top];
}
else
{
printf("StGeTop:The stack is empty!");
t=NULL;
}
return t;
}
/*将数字字符转换成整形*/
int ChrTransferint(char c)
{
int n;
switch(c)
{
case '0': n=0;break;
case '1': n=1;break;
case '2': n=2;break;
case '3': n=3;break;
case '4': n=4;break;
case '5': n=5;break;
case '6': n=6;break;
case '7': n=7;break;
case '8': n=8;break;
case '9': n=9;break;
}
return n;
}
/*获取两个操作符之间数字字符的个数,返回的是最后一个数字字符的位置*/
int GetNumsize(char str[],int n1)
{
int n2=n1;
while(isdigit(str[n2])||(str[n2])==46)/*isdigit()判断是否数字字符*/
{
n2=n2+1;
}
return n2;
}
/*判断上个函数中获得的数字字符串中是否包含小数点，并返回它的位置，不包含，返回-1*/
int IsIncludepoint(char str[],int n1,int n2)
{
int n3=-1;
int i;
for(i=n1;i<=n2;i++)
{
if(str[i]=='.')
{
n3=i;
break;
}
}
return n3;
}
/*将数字字符转换成数值*/
double Transfer(char str[],int n1,int n2,int n3)
{
double data=0;
int i,ct;
if(n3<0)
{
for(i=n2;i>=n1;i--)
{
ct=ChrTransferint(str[i]);
data=data+ct*pow(10,n2-i);/*pow(x,y)计算x的y次方的值*/
}
}
else
{
for(i=n3-1;i>=n1;i--)
{
ct=ChrTransferint(str[i]);
data=data+ct*pow(10,n3-1-i);/*pow(x,y)计算x的y次方的值*/
}
for(i=n3+1;i<=n2;i++)
{
ct=ChrTransferint(str[i]);
data=data+ct*pow(0.1,i-n3);/*pow(x,y)计算x的y次方的值*/
}
}
return data;
}
/*主程序*/
main()
{
char str[M],c;
char a;
int n,p1,p2,p3; /*n为字符串长度，p1,p2,p3分别为数字字符起始位置，结束位置，和小数点位置*/
double data; /*存放转换后的数值*/
int i=0;
Stack *so=(Stack *)malloc(sizeof(Stack)); /*存储操作符 '(':1,'+':2,'-':3, '*':4,'/':5 字符'),＝'不压栈*/
Stack *sd=(Stack *)malloc(sizeof(Stack)); /*存储操作数*/
InitStack(so);
InitStack(sd);
printf("Please input formula(format:(1+2)*1.2/4=):\n");
n=0;
while((a=getchar())!='\n')
{
str[n]=a;
n++;
}
while(i<n)
{
char c;
c=str[i];
if(c=='(')
{ /*c若是'('直接入栈so，i++*/
StPush(so,1);
i++;
}
else if(isdigit(c))
{
p1=i; /*c若是数字字符，一并将后面的连续数字字符转换为数值并压栈到sd,并把i设为后面的*/
p2=GetNumsize(str,p1);
p3=IsIncludepoint(str,p1,p2-1); /*第一个非数字字符的位置*/
data=Transfer(str,p1,p2-1,p3);
StPush(sd,data);
i=p2;
}
else if(c=='+')
{
StPush(so,2); /*c若是'+'直接入栈so,i++*/
i++;
}
else if(c=='-')
{
StPush(so,3); /*c若是'-'直接入栈so,i++*/
i++;
}
else if(c=='*')
{
if(str[i+1]=='(') /*c若是‘*’它后面的字符是否为'('，若是直接将'*'压栈so，*/
{
StPush(so,4);
i++;
}
else
{
double t1,t2,t3; /*若不是，为数字字符,将后面的连续数字字符一并转换成数值t2,sd出栈给t1,将t3=t2*t1压栈到sd*/
t1=StPop(sd); /*操作符'*'不压栈so*/
p1=i+1;
p2=GetNumsize(str,p1);
p3=IsIncludepoint(str,p1,p2-1);
t2=Transfer(str,p1,p2-1,p3);
t3=t1*t2;
StPush(sd,t3);
i=p2;
}
}
else if(c=='/')
{
if(str[i+1]=='(')
{
StPush(so,5);
i++;
}
else
{
double t1,t2,t3;
t1=StPop(sd); /*c是'/'同'*'*/
p1=i+1;
p2=GetNumsize(str,p1);
p3=IsIncludepoint(str,p1,p2-1);
t2=Transfer(str,p1,p2-1,p3);
t3=t1/t2;
StPush(sd,t3);
i=p2;
}
}
else if(c==')')
{
double t1,t2,t3;
int p;
while((p=StPop(so))!=1&&!StEmpty(so)) /*c若是')',出栈so,判断是'+'或'-',出栈sd两个操作数，进行加减运算*/
{ /*直到StPop=='('*/
t1=StPop(sd);
t2=StPop(sd);
if(p==2)
{
t3=t2+t1;
StPush(sd,t3);
}
else if(p==3)
{
t3=t2-t1;
StPush(sd,t3);
}
}
if(StGetTop(so)==4) /*然后判断so栈顶是否为'*'或者'/'*/
{
StPop(so);
t1=StPop(sd); /*为'*'出栈so,出栈 sd 获得2个操作数，进行乘法操作*/
t2=StPop(sd);
t3=t2*t1;
StPush(sd,t3);
}
else if(StGetTop(so)==5)
{
StPop(so);
t1=StPop(sd); /*为'/'出栈so,出栈 sd 获得2个操作数，进行除法操作*/
t2=StPop(sd);
t3=t2/t1;
StPush(sd,t3);
}
i++;
}
else if(c=='=')
{
double t1,t2,t3; /*c若是'='，这是so内只有加减号，出栈so到p ，sd到t1,t2*/
int p;
while(!StEmpty(so))
{
t1=StPop(sd);
t2=StPop(sd);
p=StPop(so);
if(p==2)
{
t3=t2+t1; /*p=='+',加法运算，并将结果t3压栈sd*/
StPush(sd,t3);
}
else if(p==3)
{
t3=t2-t1;
StPush(sd,t3); /*p=='-',减法运算，并将结果t3压栈sd*/
}
}
i++;
}
}
if(!StEmpty(so)||StEmpty(sd))
{
printf("Input error,Back!\n"); /*若so不为空，或者sd为空，且sd中只有一个元素,则输入的式子不对*/
}
else
{
double end;
int i; /*否则，sd中的那个数据就是最后计算结果，打印输出*/
end=StGetTop(sd);
printf("The value of this formula:\n");
for(i=0;i<n;i++)
{
printf("%c",str[i]);
}
printf("%f\n",end);
}
}
相关资讯
