洛谷P1175题解

· · 题解

update: 这篇题解是比较远古的，若还有错误欢迎纠正。已经修改过评论区中所提到的“2 * 4 + 3 在模拟的时候倒数第二行栈 op 里多了个乘号”的问题。顺便说一下，以前洛谷博客在预览时的表格确实没有线。

这题难度并不是很大，就是模拟，只是代码很长而已。只要思路明确，就可通过此题。

题目传送门

一、题意

  1. 写出给定字符串的后缀表达式。

  2. 写出计算过程。

二、数据范围

三、思路

3.1 第一问

3.1.1 认识后缀表达式的转换方法

首先，我们要知道如何手算得出后缀表达式。下面是题目样例的后缀表达式转换方法。

8 - (3 + 2 * 6) / 5 + 4
8 - (3 + 2 6 *) / 5 + 4
8 - 3 2 6 * + / 5 + 4 （去括号）
8 - 3 2 6 * + 5 / + 4 
8 3 2 6 * + 5 / - + 4
8 3 2 6 * + 5 / - 4 +

那么如何用编程来实现呢？

3.1.2 程序基本实现

用字符串 s 存储中缀表达式。

我们定义一个函数来判断运算符的优先级。如下：

int check(char c)
{
    switch(c)
    {
        case '+':return 1;
        case '-':return 1;
        case '*':return 2;
        case '/':return 2;
        case '^':return 3;
        case '(':return 0;
        case ')':return 0;
        default:return -1;//程序不会执行这句，保险起见要加上
    }
}

定义两个栈 dat 和 op，它们存的分别是后缀表达式和符号。

来看例子：2 + 3 * 4

模拟一下：

栈dat 栈op 操作
2 Null 将 2 入栈
2 + op 栈为空，将 + 入栈
3 2 + 将 3 入栈
3 2 * + * 比 + 优先级高，入栈
4 3 2 * + 将 4 入栈
+ * 4 3 2 Null 弹空 op 栈，依次进入 dat 栈

这时，逆序输出栈 dat，得到式子的后缀表达式 2 3 4 * +。

再看一个：2 * 4 + 3

栈dat 栈op 操作
2 Null 将 2 入栈
2 * op 栈为空，将 * 入栈
4 2 * 将 4 入栈
* 4 2 + + 比 * 优先级低，将 * 弹出
3 * 4 2 + 将 3 入栈
+ 3 * 4 2 Null 弹空 op 栈，依次进入 dat 栈

这时，逆序输出栈 dat，得到式子的后缀表达式 2 4 * 3 +。

经过尝试和拼凑，我们发现：

上面这些是最基本的情况。但如果有括号呢？

3.1.3 特殊情况

当 s_i 为左括号时，可以直接压进 op 栈里。当 s_i 为右括号时，一直弹出 op 栈栈顶到 dat 里，直到栈顶为左括号，再弹出左括号。这些也可以通过模拟得出答案。

看例子：2 + (3 + 4) * 3

栈 dat 栈 op 操作
2 Null 将 2 压进栈
2 + op 栈空，将 + 压进栈
2 ( + 将左括号压进栈
3 2 ( + 将 3 压进栈
3 2 + ( + + 比 ( 优先级高，将 + 压进栈
4 3 2 + ( + 将 4 压进栈
+ 4 3 2 + 将右括号与左括号之间的 + 弹出到 dat 栈
+ 4 3 2 * + * 比 + 优先级高，将 * 压进栈
3 + 4 3 2 * + 将 3 压进栈
+ * 3 + 4 3 2 Null 将 op 栈里的元素压进 dat 栈

最后逆序输出 dat 栈，得到：2 3 4 + 3 * +。

当然，我们不能忽略题目中特殊的乘方运算。模拟样例 2：2 ^ 2 ^ 3。如下：

栈 dat 栈 op 操作
2 Null 将 2 压进栈
2 ^ op 栈空，将 ^ 压进栈
2 2 ^ 将 3 压进栈
2 2 ^ ^ ^ 与 ^相同，将 ^ 压进栈（特殊）
3 2 2 ^ ^ 将 3 压进栈
^ ^ 3 2 2 Null 将 op 栈里的元素压进 dat 栈

我们得到：2 2 3 ^ ^

所以，当 s_i 为乘方运算符时且 op 栈栈顶也是乘方运算符时，也可直接压进栈中。

3.1.4 表达式输出

如果你用的是数组版栈，直接遍历即可。但如果你跟我一样用的是 STL 版栈，可以把栈 op 用来临时存放数据。先把 dat 里的元素全部压进 op 栈，再倒回来，同时输出字符即可。输出记得换行。这样，第一问就结束了。

3.2 第二问

第二问相对简单，我们同样可以定义 calc 函数完成第二问。

3.2.1 基本运算

为了方便，定义函数用来计算两个数的计算结果。这个很简单，代码如下：

int js(int x,int y,char t)//x和y为计算的两个数，t为运算符
{
    switch(t)
    {
        case '+':return x+y;
        case '-':return x-y;
        case '*':return x*y;
        case '/':return x/y;
        case '^':return pow(x,y);
        default:return -0x3f3f3f3f;//程序不会执行到这里，同样为了保险
    }
}

3.2.2 后缀表达式计算

定义两个栈 num 与 dat2，num 存储计算过程，dat2 用来临时存放数据，之前的 dat 和 op 可以继续使用。

把 dat 全部弹出到 op 里，接下来进行计算。

  1. 变量 t 获取 op 栈顶，op 弹出。

  2. 若 t 为数字，减去 '0' 再进入 num。若 t 为运算符，弹出 num 栈顶 2 个元素并记录，将运算结果压进栈，同时输出过程。

  3. 重复 1 和 2 两个步骤，直到 op 为空。

3.2.3 过程输出

输出过程时，反序输出 num，正序输出 op。

同样利用 dat2 与 dat，反序与正序差不多，只是前者在倒回来时输出，后者在倒出去时输出。最后记得换行。

四、代码

#include <bits/stdc++.h>
using namespace std;
stack<char> dat,op;
stack<int> num,dat2;
int check(char c)
{
    switch(c)
    {
        case '+':return 1;
        case '-':return 1;
        case '*':return 2;
        case '/':return 2;
        case '^':return 3;
        case '(':return 0;
        case ')':return 0;
        default:return -1;
    }
}
int js(int x,int y,char t)
{
    switch(t)
    {
        case '+':return x+y;
        case '-':return x-y;
        case '*':return x*y;
        case '/':return x/y;
        case '^':return pow(x,y);
        default:return -0x3f3f3f3f;
    }
}
void change(string s)
{
    int len=s.size();
    for(int i=0;i<len;i++)
    {
        if(isdigit(s[i]))dat.push(s[i]);
        else if(s[i]=='(')op.push(s[i]);
        else if(s[i]==')')
        {
            char t=op.top();
            while(t!='(')
            {
                op.pop();
                dat.push(t);
                t=op.top();
            }
            op.pop();//要弹出左括号
        }
        else if(check(s[i])>=1&&check(s[i])<=3)//为运算符
        {
            if(!op.empty())
            {
                char t=op.top();
                while(!op.empty()&&check(s[i])<=check(t))
                {
                    if(check(s[i])==check(t)&&s[i]=='^')break;//在s[i]与栈顶都是^号时也能进栈
                    op.pop();
                    dat.push(t);
                    if(!op.empty())t=op.top();
                }
            }
            op.push(s[i]);
        }
    }
    while(!op.empty())
    {
        char t=op.top();
        op.pop();
        dat.push(t);
    }
    while(!dat.empty())
    {
        char t=dat.top();
        dat.pop();
        op.push(t);
    }
    while(!op.empty())
    {
        char t=op.top();
        cout<<t<<' ';
        op.pop();
        dat.push(t);
    }
    cout<<endl;
}
void calc()
{
    while(!dat.empty())
    {
        char t=dat.top();
        dat.pop();
        op.push(t);
    }
    while(!op.empty())
    {
        char t=op.top();
        op.pop();
        if(isdigit(t))num.push(t-'0');
        else
        {
            int x=num.top();
            num.pop();
            int y=num.top();
            num.pop();
            num.push(js(y,x,t));//传参数时要把x和y反过来
            while(!num.empty())
            {
                int t=num.top();
                num.pop();
                dat2.push(t); 
            }
            while(!dat2.empty())
            {
                int t=dat2.top();
                cout<<t<<' ';
                dat2.pop();
                num.push(t);
            }
            while(!op.empty())
            {
                char t=op.top();
                cout<<t<<' ';
                op.pop();
                dat.push(t);
            }
            while(!dat.empty())
            {
                char t=dat.top();
                dat.pop();
                op.push(t);
            }
            cout<<endl;
        }
    }
}
int main()
{
    string s;
    cin>>s;   
    change(s);
    calc();
    return 0;
}