提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

数据结构（8）栈的应用——求值表达式

2023-02-18 16:42:48 时间

栈的应用——求值表达式

今天来写一下栈在求值表达式里的应用，这部分看了差不多一天了，具体原理基本懂了，代码实现部分只实现了无括号情况下的中缀表达式转后缀表达式，因为没找到标准的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);
}

相关文章