今天来写一下栈在求值表达式里的应用,这部分看了差不多一天了,具体原理基本懂了,代码实现部分只实现了无括号情况下的中缀表达式转后缀表达式,因为没找到标准的C代码实现,所以一直自己摸索,今天就来写一写原理以及已经实现的代码。
首先表达式分为三类,分别为:
这里的中缀,前缀,后缀指的是运算符,中缀表达式就是运算符在两个操作数中间,后缀表达式就是运算符在两个操作数后面。这里来举例。🌰例如A+B,就是一个中缀表达式,转为前缀表达式就是+AB,后缀表达式就是AB+。求值表达式的问题可以转换为两个小问题,分别用栈实现。其一是给出中缀表达式,转换为后缀表达式,其二是根据后缀表达式,求出表达式的值。
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define MaxSize 20
//建栈
typedef struct {
char data[MaxSize];
int top;
}SqStack;
//初始化
int InitList(SqStack &S){
S.top = -1;
return OK;
}
//入栈
int Push(SqStack &S,char c){
if(S.top == MaxSize -1){
return ERROR;
}
S.top = S.top + 1;
S.data[S.top] = c;
return OK;
}
//出栈
int Pop(SqStack &S,char *c){
if(S.top == -1){
return ERROR;
}
*c = S.data[S.top];
S.top = S.top - 1;
return OK;
}
//输出
int Print(SqStack S){
if(S.top == -1){
return ERROR;
}
for(int i=0;i<=S.top;i++){//小操作一手,让它逆序输出
printf("%c\t",S.data[i]);
}
printf("\n");
return OK;
}
//转换函数
int transform(char str[],int length){
SqStack S1,S2;
char c ;
InitList(S1);
InitList(S2);
for(int i=0;i<length;i++){
if(str[i] =='+' || str[i]== '-' || str[i]=='*' || str[i]=='/'){
if(S1.top == -1){
Push(S1,str[i]);
}
else{
if(str[i]=='*' || str[i]=='/'){
if(S1.data[S1.top]=='+'||S1.data[S1.top]=='-'){
Push(S1,str[i]);
}
else{
Pop(S1,&c);
Push(S2,c);
Push(S1,str[i]);
}
}
if(str[i]=='+'||str[i]=='-'){
if(S1.data[S1.top]=='+'||S1.data[S1.top]=='-' ){
Pop(S1,&c);
Push(S2,c);
Push(S1,str[i]);
}
if(S1.data[S1.top]=='*'||S1.data[S1.top]=='/'){
Pop(S1,&c);
Push(S2,c);
if(S1.top==-1){
Push(S1,str[i]);
}
else{
Pop(S1,&c);
Push(S2,c);
Push(S1,str[i]);
}
}
}
}
}
/* else if(str[i]=='(' ||str[i]==')'){
if(str[i]=='(')
Push(S1,str[i]);
else{//扫描到右括号
while(S1.data[S1.top]!='('){
Pop(S1,&c);
Push(S2,c);
if(S1.data[S1.top]=='(')
break;
}
Pop(S1,&c);//此时就剩一个左括号,把它弹出,且不放到后缀表达式里
}
}*/
else
Push(S2,str[i]);
}
if(S1.top!=-1){//循环完后S1还没空
Pop(S1,&c);
Push(S2,c);
}
Print(S1);
Print(S2);
}
//主函数及运行结果
int main (){
SqStack S1,S2;
char c;
char str[11] = {'A','+','B','-','C','*','D','/','E','+','F'};
for(int i=0;i<11;i++){
printf("%c\t",str[i]);
}
printf("\n");
transform(str,11);
}