逆波兰式的实现及表达式的值
逆波兰式的实现
1、概念
逆波兰式也叫后缀表达式,这里先简单帮大家理解一下概念性问题。
像我们平常使用到的表达式如等都是中缀表达式,对我们来说是最能理解的,但是计算机则理解起来比较困难,而其相应的后缀表达式为则更好的便于计算机的理解和处理。最直观的是用树来给大家展示:
(以为例)
通过图片发现,对树进行中序遍历得到的就是中缀表达式;对树进行后序遍历得到的就是后缀表达式,这也就是其名字的由来。想必大家一定恍然大悟了吧(嘻嘻)。
2、算法实现
1、逆波兰式
首先需要一个初始字符串、输出字符串和一个栈
对初始字符串的每一个字符进行如下处理:
- if 该字符是操作符,则直接符给输出字符串
- if 该字符是‘(’,则压入栈中
- if 该字符是‘)’,则将栈中从栈顶到最近的‘(‘之间的字符全部出栈赋给输出字符串
- while该字符是运算符:
if 栈为空或栈顶元素为’(‘或栈顶元素优先级高于该字符if栈为空或栈顶元素为’(‘或栈顶元素优先级低于该字符,将该字符压入栈中;break结束while操作
else 将栈顶元素出栈,赋给输出字符串,继续while操作 - 重复1-4的操作直到所有初始字符串均已处理
- 若栈中尚有元素,则将其栈内所有元素出栈,赋给输出字符串
- 输出输出字符串
- 操作结束
注: 在进行字符串的转换之前,先进行一次判断,也就是表达式第一个数是否是负数(即第一个字符是否为‘-’), 若是,须在‘-’前插入一个0,在进行之后的转换操作,反之,字符不做改动。
2、表达式的值
在计算过逆波兰式的基础上来求解表达式的值,计算表达式的结果。
对逆波兰式操作后获得的字符串的每个字符进行如下处理:
- if 字符是操作符,则压入栈中
- if 字符为运算符,则取出栈中最高两位进行该运算符的运算,然后将计算结果再存入栈中
- 重复1-2操作直到所有字符拘役处理
- 输出栈中余下的操作数(表达式的最终结果)
- 操作结束
3、代码实现
#include<stdio.h>
#include<malloc.h>
#include<string.h>
//定义栈
typedef struct{
char data[100];
int top;
int bottom;
}stack;
//定义全局变量
char str[10];
int n=0;
//创建栈
stack *StackCreate(){
stack *p=(stack*)malloc(sizeof(stack));//分配新空间
if(p==NULL)//分配失败
return 0;
p->bottom=p->top=0;//分配成功
return p;
}
//入栈
void StackInput(stack *p,char str){
p->data[p->top]=str;//存入栈中
p->top++;//栈顶指针加1
//printf("%c",p->data[p->top-1]);
}
//出栈
char StackOutput(stack *p,char sp){
if(p->top!=p->bottom){//栈非空
sp=p->data[p->top-1];//栈顶内容输出
p->top--;//栈顶减1
//printf("%c",str);
return sp;
}
}
//优先级比较
int prior(char a){
if(a=='+'|a=='-')
return 1;
else if(a=='*'|a=='/')
return 2;
else
return 0;
}
//逆波兰式
void rpn(char *s,stack *p){
int i,j;
char sp;
if(s[0]=='-'){//若第一个数为负数,则在其前面加一个0
for(i=0;i<strlen(s);i++)
s[strlen(s)-i]=s[strlen(s)-i-1];
s[0]='0';
}
for(i=0;i<strlen(s);i++){
if(s[i]>='0'&&s[i]<='9'){//s[i]是操作数
str[n++]=s[i];
}
if(s[i]=='('){//s[i]是左括号
StackInput(p,s[i]);
}
if(s[i]==')'){//s[i]是右括号
while(p->data[p->top-1]!='('){
str[n++]=p->data[p->top-1];
p->top--;
}
p->top--;
}
while(s[i]=='+'|s[i]=='-'|s[i]=='*'|s[i]=='/'){//s[i]是运算符
if(p->bottom==p->top|p->data[p->top-1]=='('|prior(s[i])>prior(p->data[p->top-1])){//若栈是空 或 栈顶为( 或 s[i]优先级高于栈顶元素,则入栈
StackInput(p,s[i]);
break;
}
else//反之栈顶元素出栈,继续while循环
str[n++]=StackOutput(p,sp);
}
}
while(p->bottom!=p->top){//若栈未空,将剩余的字符输出
str[n++]=p->data[p->top-1];
p->top--;
}
}
//计算表达式的值
void result(stack *p,char *str){
int i,j=0;
char sp,m,n;
for(i=0;i<strlen(str);i++){
if(str[i]>='0'&&str[i]<='9')//若为操作数,直接压入战中
StackInput(p,str[i]);
while(str[i]=='+'|str[i]=='-'|str[i]=='*'|str[i]=='/'){//若为运算符,从栈中取出两个进行运算,将结果再存入栈中
m=p->data[p->top-1];//栈顶
n=p->data[p->top-2];//栈顶下一个
p->top=p->top-2;
if(str[i]=='+')
j=((int)n-48)+((int)m-48);
if(str[i]=='-')
j=((int)n-48)-((int)m-48);
if(str[i]=='*')
j=((int)n-48)*((int)m-48);
if(str[i]=='/')
j=((int)n-48)/((int)m-48);
StackInput(p,(char)(j+48));//将结果再存入栈中
break;
}
}
printf("\n表达式的值为:\n%d",(int)p->data[p->top-1]-48);//读出最后的值
}
//主函数
int main(){
int i,j;
int r;
stack *p;//定义栈名
p=StackCreate();//创建栈
char s[10];
printf("输入中缀表达式:\n");
scanf("%s",s);
rpn(s,p);//调用逆波兰式
printf("逆波兰式为:\n");
for(i=0;i<n;i++)//输出逆波兰式
printf("%c",str[i]);
result(p,str);//进行求解表达式的值
}
//大家注入输入表达式的时候,括号千万要区分中英文,谨记
代码注释的很清楚明了,希望大家能够真正明白理解,若有何疑问请留下评论,第一时间看到就会回复。