首页 > 其他分享 >论万恶的中缀表达式转前缀

论万恶的中缀表达式转前缀

时间:2022-11-28 22:56:53浏览次数:73  
标签:case 万恶 return 中缀 clear push front empty 前缀

论万恶的中缀表达式转前缀

话说中缀表达式转后缀表达式真是一件乐事。
从CSP-J 2022 T3 来的,因为除了递归拆分,还可以用这种方法来实现对带括号的逻辑表达式进行运算。
参考了这篇博文,https://www.cnblogs.com/hantalk/p/8734511.html
几个转换的规则还是挺清楚的,但其实个人认为把第二点和第四点合成一个比较好,不然是前后冲突的。
分析了一下对面给的js代码,得出主要要实现的有这些:

  1. 比较优先级。因为这题不论是操作数还是操作符都只有一位,就偷了点懒,略去了拆分数字(秦九韶算法),还有为了方便把数字的优先级设成0.

于是便上手写,第一遍裸写,没调,出来的东西是这样的:

#include <bits/stdc++.h>
using namespace std;

queue<char> Q, P;
stack<char> S;

void clear(queue<char> &q)
{
    queue<char> empty;
    swap(empty, q);
}

void clear(stack<char> &s)
{
    stack<char> empty;
    swap(empty, s);
}

int getP(char a)
{
    switch (a)
    {
    case '0':
    case '1':
        return 0;
    case '|':
        return 1;
    case '&':
        return 2;
    case '!':
        return 3;
    case '(':
    case ')':
        return 4;
    }
}

void change(string str)
{
    clear(Q);
    clear(P);
    clear(S);
    for (int i = 0; i < str.length(); i++)
        Q.push(str[i]);
    while (!Q.empty())
    {
        if (getP(Q.front()) == 0)
        {
            P.push(Q.front());
            Q.pop();
        }
        else if (Q.front() != ')')
        {
            if (S.empty())
                S.push(Q.front());
            else
            {
                while (!S.empty() && getP(S.top()) >= getP(Q.front()) && S.top() != '(')
                {
                    P.push(S.top());
                    S.pop();
                }
                S.push(Q.front());
            }
            Q.pop();
        }
        else
        {
            //cout << S.size() << endl;
            while(S.top() != '(')
            {
                P.push(S.top());
                S.pop();
            }
            S.pop();
            Q.pop();
        }
    }
    while(!P.empty())
    {
        cout << P.front() << " ";
        P.pop();
    }
}

int main()
{
    string s = "0&(1|0)|(1|1|1&0)";
    //getline(cin , s);
    change(s);
    return 0;
}

不出所料,炸了。一查,没有把右括号弹出去,没有加判断条件.
改一下:

#include <bits/stdc++.h>
using namespace std;

queue<char> Q, P;
stack<char> S;

void clear(queue<char> &q)
{
    queue<char> empty;
    swap(empty, q);
}

void clear(stack<char> &s)
{
    stack<char> empty;
    swap(empty, s);
}

int getP(char a)
{
    switch (a)
    {
    case '0':
    case '1':
        return 0;
    case '|':
        return 1;
    case '&':
        return 2;
    case '!':
        return 3;
    case '(':
    case ')':
        return 4;
    }
}

void change(string str)
{
    clear(Q);
    clear(P);
    clear(S);
    for (int i = 0; i < str.length(); i++)
        Q.push(str[i]);
    while (!Q.empty())
    {
        if (getP(Q.front()) == 0)
        {
            P.push(Q.front());
            Q.pop();
        }
        else if (Q.front() != ')')
        {
            if (S.empty())
                S.push(Q.front());
            else
            {
                while (!S.empty() && getP(S.top()) >= getP(Q.front()) && S.top() != '(')
                {
                    P.push(S.top());
                    S.pop();
                }
                S.push(Q.front());
            }
            Q.pop();
        }
        else
        {
            //cout << S.size() << endl;
            while(S.top() != '(')
            {
                P.push(S.top());
                S.pop();
            }
            S.pop();
            Q.pop();
        }
    }
    while(!P.empty())
    {
        cout << P.front() << " ";
        P.pop();
    }
    
}

int main()
{
    string s = "0&(1|0)|(1|1|1&0)";
    //getline(cin , s);
    change(s);
    return 0;
}

这便是好了。

标签:case,万恶,return,中缀,clear,push,front,empty,前缀
From: https://www.cnblogs.com/liziyu0714/p/16885505.html

相关文章

  • 区间DP-前缀和优化-2478. 完美分割的方案数
    问题描述给你一个字符串 s ,每个字符是数字 '1' 到 '9' ,再给你两个整数 k和 minLength 。如果对s 的分割满足以下条件,那么我们认为它是一个完美 分割:s 被......
  • [置换 前缀和]牛牛的猜球游戏
    [置换前缀和]牛牛的猜球游戏题目思路参考​​这篇题解​​​代码很简易,但是感觉还是有点难想到awa对于广义的前缀和来说,sum[r]就是到第r次操作为止,操作累积造成的影响。......
  • P5369 [PKUSC2018]最大前缀和
    P5369[PKUSC2018]最大前缀和题目要我们求每一种排列的最大前缀和,不妨考虑先确定最大前缀和,再计算它的方案数,设\(U\)为全集,那么答案就为\(\sum_{S\subseteqU}sum[S]*f......
  • [NEFU ACM大一暑假集训 解题报告]前缀和与差分
    [NEFUACM大一暑假集训解题报告]前缀和与差分题量略大,所以解题报告和fjy大佬分了一下工由我负责A-K部分题解(不是AK部分题解啊,哈哈)后半部分题解(LM+R~V+XYZ)由fjy大佬发布......
  • 中缀表达式求值
    中缀表达式指的是形如(15+(32-1)×5+14÷2)的表达式,这种就是我们通常见到的书写算式顺序,但在实际的计算机运算中要计算中缀表达式则首先要将字符串转换为后缀表达式,然后......
  • 212. 单词搜索 II(字典树/前缀树)
    给定一个 mxn 二维字符网格 board 和一个单词(字符串)列表 words, 返回所有二维网格上的单词 。单词必须按照字母顺序,通过 相邻的单元格 内的字母构成,其中“相邻......
  • 2022NOIP A层联测33 GCD 简单题 建筑 树上前缀和
    T1:[图论/枚举]给出有边权无向图,边权保证互不相同,Q次询问从S到T的路径中,边权的gcd最大是多少。(n<=1e4,Q<=2e5,w<=1e6)考场根据之前的一道图论题经验,在最短路上加个“\(w......
  • TM4C123G学习记录(4)--关于ROM前缀函数和HWREG函数
    为了准备电赛临时学一下TM4C123G,简单记录学习内容大家可以在​​这里​​下载我收集的资源,非常全面,花了很大功夫收集来的,还有书籍、例程代码等还可以在TI官网下载相关文档​......
  • 牛客小白月赛61 F 尺取法 前缀和
    题目的描述是多维的即有人数限制又有座位限制。但是每次选座位是连续的,这意味着可以利用尺取法贪心的求出以每个左端点为起始最小的合法的右端点。考虑如何求f(x)即x人......
  • leetcode_Day1_14最长公共前缀
    1.题目  2.解一  主要思路:横向比较,字符串数组的公共前缀等于前两个字符串的公共前缀与第三个字符串比较,再与第四个比较。即依次遍历字符串数组中的每个字符串,对......