表达式求值(栈和队列)

待我称王封你为后i 2022-03-30 04:27 272阅读 0赞

###  ###

题目描述

利用栈来实现含有加，减，乘，除等基本运算，输出表达式的值(乘是字母x)

输入

3x(15/5)+8

输出

样例输入 Copy

24-\[6+(27/3)x2\]

样例输出 Copy

##### 分析： #####

此题无疑多加了一个‘\[\]’。基本思路还是一样的，但是注意，此题的乘是‘X’。而不是’\*‘。这是要点。基本思路还是逆波兰。\`

#include"stdio.h"
    #include"string.h"
    #define MAX_lenght 10000
    typedef struct
    {
        double data[MAX_lenght];
        int top;
    } SqStack;//数字的存入。
    typedef struct
    {
        char data[MAX_lenght];
        int top;
    } SqStackchar;//符号的存入
    SqStack S;
    SqStackchar Symbol;
    void PUSHchar(char t)
    {
    
        {
    
            Symbol.data[Symbol.top]=t;
            Symbol.top++;
    
        }
    }
    void POPchar(char *t)
    {
    
        {
            *t=Symbol.data[Symbol.top-1];
            Symbol.top--;
        }
    }
    void PUSH(double e)
    {
    
        {
    
            S.data[S.top]=e;
             S.top++;
    
        }
    }
    void POP(double *e)
    {
    
        {
            *e=S.data[S.top-1];
            S.top--;
        }
    }
    void change(char e)
    {
        double a,b,c;
        char t;
        if((e=='+'||e=='-')&&Symbol.top>0)
        {
           t=1;
            while(Symbol.top>0&&t!='('&&t!='[')
            {
                 POPchar(&t);
                 if((t=='('||t=='['))
                        break;
                POP(&a);
                POP(&b);
                switch(t)
                {
                    case '+': PUSH(a+b);break;
                    case '-': PUSH(b-a);break;
                    case 'x': PUSH(a*b);break;
                    case '/': PUSH(b/a);break;
                }
    
            }
            if(t=='('||t=='[')
                PUSHchar(t);
          PUSHchar(e);
        }
        else
        if((e=='x'||e=='/')&&Symbol.top>0)
        {
    
            t=1;
            while(Symbol.top>0&&t!='('&&t!='['&&t!='+'&&t!='-')
            {
                POPchar(&t);
                if(t=='('||t=='['||t=='+'||t=='-')
                     break;
                POP(&a);
                POP(&b);
                switch(t)
                {
                    case '+': PUSH(a+b);break;
                    case '-': PUSH(b-a);break;
                    case 'x': PUSH(a*b);break;
                    case '/': PUSH(b/a);break;
                }
    
            }
            if(t=='('||t=='['||t=='+'||t=='-')
                PUSHchar(t);
        PUSHchar(e);
        }
        else
        if(e==')')
        {
            t=1;
            while(Symbol.top>0&&t!='(')
            {
                POPchar(&t);
                if(t=='(')
                    break;
                POP(&a);
                POP(&b);
                switch(t)
                {
                    case '+': PUSH(a+b);break;
                    case '-': PUSH(b-a);break;
                    case 'x': PUSH(a*b);break;
                    case '/': PUSH(b/a);break;
                }
              POPchar(&t);
            }
    
        }
        else
        if(e==']')
        {
            t=1;
            while(t!='[')
            {
                POPchar(&t);
                if(t=='[')
                    break;
                POP(&a);
                POP(&b);
                switch(t)
                {
                    case '+': PUSH(a+b);break;
                    case '-': PUSH(b-a);break;
                    case 'x': PUSH(a*b);break;
                    case '/': PUSH(b/a);break;
                }
    
            }
        }
        else
            PUSHchar(e);
    
    }
    int main()
    {
        char a[1000];
        int i,len,k;
        char t;
        double digit,x,y;
        while(~scanf("%s",a))
        {
            len=strlen(a);
            digit=0;S.top=0;Symbol.top=0;
            for(i=0;i<len;i++)
            {
                digit=0;
                while(a[i]>='0'&&a[i]<='9'&&a[i]!='\0')
                    {
                        digit=digit*10+(a[i]-'0');
                        i++;
    
                    }
    
                PUSH(digit);
    
                while(!(a[i]>='0'&&a[i]<='9')&&a[i]!='\0')
                {
                    change(a[i]);
                    i++;
                }
    
    
                if(a[i]!='\0')
                    i--;
    
    
            }
    
            while(Symbol.top>0)
            {
                POPchar(&t);
                POP(&x);
                POP(&y);
                switch(t)
                {
                    case '+': PUSH(x+y);break;
                    case '-': PUSH(y-x);break;
                    case 'x': PUSH(x*y);break;
                    case '/': PUSH(y/x);break;
                }
    
            }
    
           POP(&x);
        printf("%0.0lf\n",x);
        }
    }