洛谷P1175 表达式的转换

- 44通过
- 147提交
题目提供者该用户不存在
标签云端
难度提高+/省选-
时空限制1s / 128MB

讨论题解

题目描述

平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而中缀表达式就不必用括号了。

后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。

例如：8–(3+2*6)/5+4可以写为：8 3 2 6*+5/–4+

其计算步骤为：8 3 2 6 * + 5 / – 4 +

8 3 12 + 5 / – 4 +

8 15 5 / – 4 +

8 3 – 4 +

5 4 + 9

编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。

输入输出格式

输入格式：

就一行，是一个中缀表达式。输入的符号中只有这些基本符号“0123456789+-*/^()”，并且不会出现形如2*-3的格式。

表达式中的基本数字也都是一位的，不会出现形如12形式的数字。

所输入的字符串不要判错。

输出格式：

若干个后缀表达式，第I+1行比第I行少一个运算符和一个操作数，最后一行只有一个数字，表示运算结果。

输入输出样例

输入样例#1：

8–(3+2*6)/5+4

输出样例#1：

8 3 2 6 * + 5 / – 4 + 
8 3 12 + 5 / – 4 + 
8 15 5 / – 4 + 
8 3 – 4 + 
5 4 + 
9

说明

运算的结果可能为负数，“/”以整除运算。并且中间每一步都不会超过2^31。

分析：中缀表达式转换为后缀表达式的一个解法：

0.定义一个栈.

1.遇到数，输出.

2.碰到左括号，直接压到栈顶.

3.碰到一个运算符，如果栈顶元素是左括号，直接压入栈顶，否则，从栈顶开始，把比这个运算符优先级大的给输出，然后压进去.

4.碰到右括号，将元素不断弹出直到遇到左括号.

那么如何进行计算呢？可以发现运算符是按照运算先后顺序出现的，我们只需要将字符串转化为数字，然后枚举到运算符直接运算及可.

#include <iostream>  
#include <cstdlib>  
#include <cstdio>  
#include <cstring>  
#include <string>  
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

string s,s1;
int sizee,top,num[10000010];

stack <char> k;

void add(char ss)
{
    s1 += ss;
    s1 += ' ';
}

bool check(char t)
{
    if (k.empty() || k.top() == '(')  //千万不要打反了，血的教训
        return true;
    if (k.top() == '^')
        return false;
    if (t == '^')
        return true;
    if (k.top() == '*' || k.top() == '/')
        return false;
    if (t == '*' || t == '/')
        return true;
    return false;
}

void jisuan(char x)
{
    int a = num[top--], b = num[top--],t = 0;
    if (x == '+')
        t = a + b;
    if (x == '-')
        t = b - a;
    if (x == '*')
        t = a * b;
    if (x == '/')
        t = b / a;
    if (x == '^')
        t = pow(b, a);
    num[++top] = t;
}

void solve()
{
    for (int i = 0; i < sizee; i++)
    {
        if (s[i] >= '0' && s[i] <= '9')
            add(s[i]);
        else
        {
            if (s[i] == '(')
                k.push(s[i]);
            else
            {
                if (s[i] == ')')
                {
                    while (k.top() != '(')
                    {
                        add(k.top());
                        k.pop();
                    }
                    k.pop();
                }
                else
                {
                    if (!check(s[i]))
                    {
                        while (!check(s[i]))
                        {
                            add(k.top());
                            k.pop();
                        }
                    }
                    k.push(s[i]);
                }
            }
        }
    }
    while (!k.empty())
    {
        add(k.top());
        k.pop();
    }
    cout << s1 << endl;
}

void print()
{
    for (int i = 0; i < s1.size(); i++)
    {
        if (s1[i] >= '0' && s1[i] <= '9')
            num[++top] = s1[i] - '0';
        else
        {
            if (s1[i] == ' ')
                continue;
            jisuan(s1[i]);
            i++;
            for (int j = 1; j <= top; j++)
                printf("%d ", num[j]);
            for (int j = i + 1; j < s1.size(); j++)
                printf("%c", s1[j]);
            cout << endl;
        }
    }
}

int main()
{
    cin >> s;
    sizee = s.size();
    solve();
    print();

    return 0;
}