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

小咪咪 2022-06-07 08:53 57阅读 0赞

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

Time Limit: 1000MS Memory Limit: 65536KB

#### Problem Description ####

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

#### Input ####

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

#### Output ####

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

#### Example Input ####

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

#### Example Output ####

ab*cde/-f*+

#include <bits/stdc++.h>
    
    using namespace std;
    #define intsize 100000
    #define addsize 100000
    typedef char elemtype;
    
    typedef struct
    {
        elemtype *base;
        elemtype *top;
        int stacksize;
    }sqstack;
    
    int bian(char n)
    {
        int flag;
        if(n=='(') flag = 1;
        if(n==')') flag = 4;
        if(n=='+') flag = 2;
        if(n=='-') flag = 2;
        if(n=='*') flag = 3;
        if(n=='/') flag = 3;
        return flag;
    }
    
    int initstack(sqstack &s)
    {
        //s.base = (elemtype *)malloc(intsize*sizeof(elemtype));
        s.base = new elemtype[intsize];
        if(!s.base) return -1;
        s.top = s.base;
        s.stacksize = intsize;
        return 0;
    }
    
    void push(sqstack &s, elemtype x)
    {
        /*if(s.top-s.base > s.stacksize)
        {
            s.base = new elemtype[intsize+addsize];
            if(!s.base) return -1;
            s.top = s.base + addsize;
            s.stacksize += addsize;
        }*/
        *s.top++ = x;
    }
    
    char pop(sqstack &s)
    {
        char x;
        return x = *--s.top;
    }
    
    void change(sqstack &s,char n)
    {
        if(n=='(')
        {
             push(s,n);
        }
        else if(n==')')
        {
            while(1)
            {
                if(*(s.top-1)=='(')
                {
                    pop(s);break;
                }
                else
                {
                    cout << pop(s);
                }
            }
        }
        else if(bian(*(s.top-1))< bian(n))
        {
            push(s,n);
        }
        else if(bian(*(s.top-1))>= bian(n))
        {
            cout << pop(s);
            push(s,n);
        }
    }
    
    void show(sqstack &s)
    {
        while(s.top!=s.base)
        {
            cout << pop(s);
        }
        cout << endl;
    }
    
    int main()
    {
        sqstack s;
        char n;
        initstack(s);
        while(~scanf("%c",&n)&&n!='#')
        {
            if(n>='a' && n<='z')
            {
                cout << n;
            }
            else
            {
                change(s,n);
            }
        }
        show(s);
        return 0;
    }