题解 P1175 【表达式的转换】

· · 题解

前置知识：求后缀表达式的值。 代码：

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1010;
ll sta[N],x;int top;
char s[N];
int main()
{
    scanf("%s",s+1);
    for(int i=1;s[i]!='@';i++)
    {
        if('0'<=s[i]&&s[i]<='9')
        {
            x=0;
            while(s[i]!='.')x=x*10+s[i++]-'0';
            sta[++top]=x;
        }
        else
        {
            x=sta[top--];ll &y=sta[top];
            if(s[i]=='+')y+=x;
            else if(s[i]=='-')y-=x;
            else if(s[i]=='*')y*=x;
            else if(s[i]=='/')y/=x;
        }
    }
    printf("%lld\n",sta[1]);
    return 0;
}

这题最麻烦的就是把中缀表达式转化成后缀表达式，难点是处理优先级的问题。 我们从左往右扫描中缀表达式，进行如下处理：

1.

建立一个符号栈ops和一个存后缀表达式的字符串p。

2.

如果是数字则加入p，因为形为"A~~ op~~ B"的中缀表达式转成后缀表达式就成了"A~~ B~~ op",数字一定在前。

3.

如果是左括号，则加入ops。

4.

如果是右括号，则把符号栈中的运算符弹到p，直到遇到最近的左括号。最后，把一个左括号删除(不入p）。

5.

如果是运算符，则把优先级大于或等于的栈顶符号弹入p。因为这样能保证优先级高的先算。

为什么，优先级等于也要弹出呢？因为同级运算从左往右啊。

6.

重复2~~~5，直到扫描完毕。

7.

把剩下的符号依次弹入s。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<stack>
#define ll long long//不超过2^31——等于2^31会爆int 
using namespace std;
const int N=1e3+10;
//思路：把中缀表达式转成后缀表达式，再对后缀表达式进行处理。
//每处理一次运算，把数值栈中的数字输出，并把未处理的符号、数字输出。 

char s[N];//中缀表达式
stack<char>ops;//符号栈
char p[N];int pl;//postfix Expression 后缀表达式
ll sta[N];int top;//数值栈

int grade(char op)//优先级 
{
    switch(op){
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
        return 2;
    case '^':
        return 3;
    }
    return 0;
}

void calc(char op)//计算 
{
    ll x=sta[top--],y=sta[top];
    switch(op){
        case '+':
            y+=x;
            break;
        case '-':
             y-=x;
             break;
        case '*':
             y*=x;
             break;
        case '/':
             y/=x;
             break;
        case '^':
            y=pow(y,x);
        }
    sta[top]=y;
}

int main()
{
    scanf("%s",s);int n=strlen(s);
    for(int i=0;i<n;i++)
    {
        char c=s[i];
        if('0'<=c&&c<='9')p[++pl]=c;//数字 
        else
        {
            //括号 
            if(c=='(')ops.push(c);
            else if(c==')')
            {
                while(ops.size()&&(c=ops.top())!='(')
                {
                    p[++pl]=c;
                    ops.pop();
                }
                ops.pop();
            }
            else//运算符 
            {
                while(ops.size()&&grade(ops.top())>=grade(c))
                {
                    p[++pl]=ops.top();
                    ops.pop();
                }
                ops.push(c);
            }
        }
    }
    while(ops.size())p[++pl]=ops.top(),ops.pop();
    for(int i=1;i<=pl;i++)printf("%c ",p[i]);
    puts("");//输出中缀表达式

    for(int i=1;i<=pl;i++)//逐步处理后缀表达式 
    {
        char c=p[i];
        if('0'<=c&&c<='9')sta[++top]=c-'0';
        else//运算符 
        {
            calc(c);
            for(int j=1;j<=top;j++)printf("%lld ",sta[j]);
            for(int j=i+1;j<=pl;j++)printf("%c ",p[j]);
            puts("");   
        }
    }

    return 0;
}