题解 P1175 【表达式的转换】

· · 题解

这个程序绝对是我有史以来写过最长的程序。
没有之一
但肯定比楼下的短
总之分两段
a）中缀表达式转后缀表达式：五类
1.遇到操作数直接输出 2.遇到左括号，左括号入栈，栈内的优先级最低
3.遇到右括号，持续出栈操作，不停pop直至遇到左括号
4.如果是数字，不停地pop，直到遇到栈内优先级低于入栈符号的符号为止
5.扫完，将符号栈内所有剩余符号出栈输出
b）后缀表达式求值
1.每次只找到第一个运算符号，然后往前查到两个运算数
2.对两个运算数进行与运算符号相同的运算，将这一对运算数和它们的运算符去掉，把运算结果放回原处。

#include<bits/stdc++.h>
using namespace std;
int q[1000001],top;
int l,order[128];
char s[10000],a[10001];
void push(char x)
{
    q[++top]=x;
}
char pop()
{
    top--;
    return q[top+1];
}
void push2(int x)
{
    q[++top]=x;
}
int pop2()
{
    top--;
    return q[top+1];
}
int main ()
{
    order['+']=order['-']=1;
    order['*']=order['/']=2;
    order['^']=3;
    scanf("%s",s);
    int n=strlen(s);
    for(int i=0;i<n;i++){
        if(s[i]<='9'&&s[i]>='0') a[++l]=s[i];
        else {
            if(s[i]=='(') push('(');
            if(s[i]==')') {
                while (q[top]!='(') a[++l]=pop();
                pop();
            } 
            if(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='^'){
                while(order[s[i]]<=order[q[top]]) a[++l]=pop();
                push(s[i]);
            }
        }
        if(i==n-1) while(top!=0) a[++l]=pop();
    }
    for(int i=1; i<=l; i++){
        printf("%c ",a[i]);
        s[i-1]=a[i];
    }
    printf("\n");
    for(int i=l;i<n;i++){
        s[i]='\0';
    }
    top=-1;
    int len=l;
    for(int i=0;i<len;i++) {
        if(s[i]>='0'&&s[i]<='9') {
            push2(s[i]-'0');
            continue;
        }
        int x=pop2();
        int y=pop2();
        if(s[i]=='+') push2(y+x);
        if(s[i]=='-') push2(y-x);
        if(s[i]=='*') push2(y*x);
        if(s[i]=='/') push2(y/x);
        if(s[i]=='^') {
            int z=1;
            for(int j=1;j<=x;j++)
                z=z*y;
            push2(z);
        }
        for(int j=0;j<=top;j++) printf("%d ",q[j]);
        for(int j=i+2;j<=len;j++) printf("%c ",a[j]);
        printf("\n");
    }
//  printf("%d",q[0]);
    return 0;
}