MT3035 逆波兰式

简介: MT3035 逆波兰式

eb7b2e5685e1472d86786ff64a3503cb.jpg

eee0119b49b94555869139c85c6151d1.jpg

思路:


两个栈str1和sr2,分别存放运算符和结果。

如果是数字,直接放入str2中。

如果是运算符:

1. ( :直接放入   str1

2. +/-/*// 看栈顶元素,若当前字符优先级比栈顶大,则压到str1中;否则str1中元素出栈压到str2中直到当前字符优先级比栈顶大,再把当前字符压到str1中。

3. ) :str1元素依次出栈压到str2中,直到碰见( 。  


例子:8-(3+2*6)/5+4


str1:                                             str2: 8          

str1:-                                            str2: 8          

str1:-  (                                         str2: 8  

str1:-  (                                         str2: 8 3  

str1:-  ( +                                      str2: 8 3  

str1:-  ( +                                      str2: 8 3 2

str1:-  ( +  *                                   str2: 8 3 2

str1:-  ( +  *                                   str2: 8 3 2 6

此时遇见):

str1:-                                             str2: 8 3 2 6 * +

str1:-  /                                          str2: 8 3 2 6 * +

str1:-  /                                          str2: 8 3 2 6 * + 5

此时遇见+,因为str1栈顶为/,所以要把/放到str2;str1栈顶此时为-,因为+不比-优先级高,所以-也放入str2中:

str1: +                                        str2: 8 3 2 6 * + 5  / -

str1: +                                        str2: 8 3 2 6 * + 5  / - 4

最后把str1中元素依次压到str2中:

str1:                                          str2: 8 3 2 6 * + 5  / - 4 +

所以最后str2中元素逆序出栈即为逆波兰式。


代码:


#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
bool is_op(char c)
{
    return c == '+' || c == '-' || c == '*' || c == '/';
}
int prority(char op)
{
    if (op == '+' || op == '-')
        return 1;
    if (op == '*' || op == '/')
        return 2;
    return -1;
}
void process_op(string s)
{ // 后缀表达式的求值
    stack<int> st;
    bool change = false; // 记录是否需要打印
    for (int i = 0; i < s.length(); i++)
    {
        if (is_op(s[i]))
        {
            int r = st.top();
            st.pop();
            int l = st.top();
            st.pop();
            switch (s[i])
            {
            case '+':
                st.push(l + r);
                break;
            case '-':
                st.push(l - r);
                break;
            case '*':
                st.push(l * r);
                break;
            case '/':
                st.push(l / r);
                break;
            }
            change = true; // 计算,需要打印
        }
        else
        {
            st.push(s[i] - '0'); // 数字入栈
            change = false;      // 不需打印
        }
        if (change)
        { // 打印后缀表达式
            stack<int> temp1, temp2;
            temp1 = st;
            while (!temp1.empty())
            { // 将栈中元素倒序
                temp2.push(temp1.top());
                temp1.pop();
            }
            while (!temp2.empty())
            { // 打印计算的前半段
                cout << temp2.top() << " ";
                temp2.pop();
            }
            for (int j = i + 1; j < s.length(); j++)
            { // 打印未计算的后半段
                cout << s[j] << " ";
            }
            cout << endl;
        }
    }
}
string toRPN(string s)
{                   // 中缀转后缀
    stack<char> st; // 结果栈
    stack<char> op; // 操作数栈
    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '(')
        {
            op.push(s[i]);
        }
        else if (s[i] == ')')
        {
            while (op.top() != '(')
            {
                st.push(op.top());
                op.pop();
            }
            op.pop(); // 弹出'('
        }
        else if (is_op(s[i]))
        {
            while (!op.empty() && prority(op.top()) >= prority(s[i]))
            { // 当前符号不比栈顶符号优先级高
                st.push(op.top());
                op.pop();
            }
            op.push(s[i]);
        }
        else // 数字
        {
            st.push(s[i]);
        }
    }
    while (!op.empty())
    { // 最后把op中的符号全部弹出压入st
        st.push(op.top());
        op.pop();
    }
    // 逆序放到ans中
    string ans;
    int len = st.size();
    while (len--)
    {
        ans = st.top() + ans;
        st.pop();
    }
    return ans;
}
int main()
{
    string s;
    cin >> s;
    string s2 = toRPN(s); // 存放逆波兰式
    for (int i = 0; i < s2.length(); i++)
    {
        cout << s2[i] << " ";
    }
    cout << endl;
    process_op(s2);
    return 0;
}


相关文章
|
Java Android开发 C++
Rockchip系列之CAN 新增framework系统jni接口访问(2)
Rockchip系列之CAN 新增framework系统jni接口访问(2)
181 3
|
算法
如何写数学建模竞赛论文
如何写数学建模竞赛论文
156 0
|
机器学习/深度学习 传感器 算法
基于干部-群众关系的教与学优化算法TLOCTO求解单目标优化问题附matlab代码
基于干部-群众关系的教与学优化算法TLOCTO求解单目标优化问题附matlab代码
|
11月前
|
机器学习/深度学习 并行计算 Linux
环境安装(二):不同平台皆可安装Paddle
这篇文章介绍了如何在不同操作系统平台上安装PaddlePaddle,包括Windows和Linux,以及如何使用Paddle Lite在AMD64和ARM架构上部署模型,并提供了官方安装命令和进一步学习资源。
867 0
|
Serverless
在函数计算FC单论sd的话,a10效率和价格分别是t4的多少倍?
在函数计算FC单论sd的话,a10效率和价格分别是t4的多少倍?
403 1
|
弹性计算 Ubuntu Linux
阿里云上自建幻兽帕鲁Palworld服务器,详细指南
在神秘的幻兽世界中,与好友并肩作战,探索未知的乐趣无疑是每位玩家的梦想。但官方服务器的限制与不稳定,时常让这份梦想蒙上阴影。此刻,阿里云为您带来完美解决方案——自建幻兽帕鲁服务器,让您与战友在专属的云端空间中畅享游戏乐趣!
128 0
|
机器人 Java
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
109 0
每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
|
XML Java 关系型数据库
SpringBoot读写分离
SpringBoot读写分离
175 0
SpringBoot读写分离
|
C语言
C语言刷题系列——2.输入输出练习
C语言刷题系列——2.输入输出练习
245 0
《Towards Language-Universal Mandarin-English Speech Recognition》电子版地址
Towards Language-Universal Mandarin-English Speech Recognition
107 0
《Towards Language-Universal Mandarin-English Speech Recognition》电子版地址