2.c

栈和队列的操作与应用

#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
void trans(char *exp,char *postexp)
{
    struct
    {
        char data[MaxSize];
        int top;
    } op;
    int i=0;
    op.top=-1;
    while(*exp!='\0')
    {
        switch(*exp)
        {
            case '(':
                op.top++;op.data[op.top]=*exp;
                exp++;break;
            case ')':
                while(op.data[op.top]!='(')
                {
                    postexp[i++]=op.data[op.top];
                    op.top--;
                }            
                op.top--;exp++;break;    
            case '+':
            case '-':
                while(op.top!=-1&&op.data[op.top]!='(')
                {
                    postexp[i++]=op.data[op.top];
                    op.top--;
                }        
                op.top++;op.data[op.top]=*exp;exp++;break;
            case '*':
            case '/':
                while(op.data[op.top]=='*'||op.data[op.top]=='/')
                {
                    postexp[i++]=op.data[op.top];
                    op.top--;
                } 
                op.top++;op.data[op.top]=*exp;exp++;break;
            case ' ':break;
            default:
                while(*exp>='0'&&*exp<='9')
                {
                    postexp[i++]=*exp;
                    exp++;
                }     
                postexp[i++]='#';
        }    
    }   
    while(op.top!=-1)
    {
        postexp[i++]=op.data[op.top];
        op.top--;
    }   
    postexp[i]='\0'; 
}   
float compvalue(char *postexp)
{
    struct
    {
        float data[MaxSize];
        int top;
    } st;
    float a,b,c,d;
    st.top=-1;
    while(*postexp!='\0')
    {
        switch(*postexp)
        {
            case '+':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                c=b+a;
                st.top++;
                st.data[st.top]=c;
                break;
            case '-':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                c=b-a;
                st.top++;
                st.data[st.top]=c;
                break;
            case '*':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                c=b*a;
                st.top++;
                st.data[st.top]=c;
                break;
            case '/':
                a=st.data[st.top];
                st.top--;
                b=st.data[st.top];
                st.top--;
                if(a!=0)
                {
                    c=b/a;
                    st.top++;
                    st.data[st.top]=c;
                }    
                else
                {
                    printf("\n\t除零错误!\n");
                    exit(0);
                }    
                break;
            default:
                d=0;
                while(*postexp>='0'&&*postexp<='9')
                {
                    d=10*d+*postexp-'0';
                    postexp++;
                }    
                st.top++;
                st.data[st.top]=d;
                break;
        }    
        postexp++;
    }    
    return st.data[st.top];
}   
int main()
{
    char exp[MaxSize],postexp[MaxSize];
    while(scanf("%s",&exp)!=EOF)
    {
        trans(exp,postexp);
        printf("中缀表达式为:%s\n",exp);
        printf("后缀表达式为:%s\n",postexp);
        printf("值为:%g\n",compvalue(postexp));
    }    
    return 0;
}