数据结构实验之栈二：一般算术表达式转换成后缀式

野性酷女 2022-09-25 07:23 43阅读 0赞

## 数据结构实验之栈二：一般算术表达式转换成后缀式 ##

####  ####

#### Time Limit: 1000MS Memory limit: 65536K ####

## 题目描述 ##

对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。

## 输入 ##

输入一个算术表达式，以‘\#’字符作为结束标志。

## 输出 ##

输出该表达式转换所得到的后缀式。

## 示例输入 ##

a*b+(c-d/e)*f#

## 示例输出 ##

ab*cde/-f*+

代码

#include<stdio.h>
    #include<stdlib.h>
    #define stackmax 10000
    #define stacknum 10000
    typedef struct  //栈函数
    {
        char *top;
        char *base;
        int stacksize;
    }stack;
    int initstack(stack &s)  //函数初始化
    {
        s.base = (char *)malloc(stackmax*sizeof(char));
        if(!s.base) exit(0);
        s.top = s.base;
        s.stacksize = stackmax;
        return 1;
    }
    void push(stack &s,char e)  //进栈函数
    {
        if(s.top - s.base > s.stacksize)
        {
            s.base = (char *)malloc((stackmax + stacknum)*sizeof(char));
            if(!s.base)exit(0);
            s.top = s.base + s.stacksize;
            s.stacksize += stacknum;
        }
        *s.top++ = e;
    }
    void pop(stack &s)  //出栈函数
    {
        s.top--;
        printf("%c",*s.top);
    }
    void choose(stack &s,char str[])  
    {
        for(int i = 0;str[i] != '#';i++)                     //遍历整个字符串
        {
            if(str[i] >= 'a' && str[i] <= 'z')               //遇到字母字节输出，排列顺序不变
            {
                printf("%c",str[i]);
            }
            else if(str[i] == '*' || str[i] == '/')          //遇到* / ，优先级高，直接进栈
            {
                push(s,str[i]);
            }
            else if(str[i] == '+' || str[i] == '-')         //遇到+ - ,检索是否是在栈顶的是否优先级高，
            {
                if(*(s.top-1) == '*' || *(s.top-1) == '/')  //如果是的话输出优先级高的* 或/
                {
                    pop(s);
                }
                push(s,str[i]);                             //然后进栈
            }
            else if(str[i] == '(')                          //遇到左括号进栈
            {
                push(s,str[i]);
            }
            else if(str[i] == ')')                          //遇到右括号出栈
            {
                while(*(s.top-1) != '(')                    //一直遇到左括号停止出栈
                {
                    pop(s);
                }
                s.top--;
            }
        }
        while(s.top != s.base)         //输出栈内的字符
        {
            pop(s);
        }
        printf("\n");
    }
    int main()
    {
        stack s;
        char str[stackmax];
        gets(str);
        initstack(s);
        choose(s,str);
        return 0;
    }