精华内容
下载资源
问答
  • 本文实例为大家分享了C++实现中缀表达式后缀表达式的具体代码,供大家参考,具体内容如下 题目:现有中缀表达式如:1+(2-3)*4+10/5 请用栈的特性编写一个程序,使得程序输出后缀表达式 分析如下: STEP1: 1+(2-3)...
  • 主要为大家详细介绍了C++实现中缀表达式后缀表达式,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 中缀表达式转换为后缀表达式(oj题库) 中缀表达式转换为后缀表达式(oj题库) 题目描述 中缀表达式是一个通用的算术或逻辑公式表示方法,操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的...
  • (1) 从键盘或文件读入一个合法的算术表达式,输出相应的后缀表达式后缀表达式中,数据与数据之间加分隔符; (2) 输出正确的计算结果,保留两位小数点; (3) 考虑算法的健壮性,当表达式错误时,要给出错误...
  • 先写词法分析的源文件,用正则表达式表示出需要识别的字符,例如数字,乘法,加法和括号,如果识别到其他非法字符需要报错,用flex生成lex.yy.c文件。语法分析用LR方法进行语法分析,LR方法需要先根据文法构造自动机...
  • NULL 博文链接:https://128kj.iteye.com/blog/1623312
  • 安装Parser Generator软件,熟悉其使用,对讲义中简单表达式计算的Yacc...3.修改Yacc程序,不进行表达式的计算,而是实现中缀表达式后缀表达式的转换。 C语言版,包含.y和对应的两个.h,.c文件,在VS2013上编译成功。
  • c语言实现中缀表达式后缀表达式并求得计算结果,用顺序栈结构。 当输入者输入错误信息的时候需要报错,并说明错误的种类。
  • 该程序实现了运算表达式转换为中缀表达式中缀表达式转换为后缀表达式后缀表达式求值。该程序已实现加减乘除括号运算符及求余、幂指数的求解
  • 用dev c++写的代码,附有啰里啰嗦的注释和测试样例。太简单了不好意思要分。
  • 表达式2*(9+6/3-5)+4,称为中缀表达式,表示成2 9 6 3 / + 5 - * 4 +称为后缀表达式,表示成+ * 2 - + 9 / 6 3 5 4称为前缀表达式。 ·基本要求 将中缀表达式,转换为后缀表达式和前缀表达式,再分别计算转换后的...
  • 表达式树的形式进行编码,能够输出结点和右节点,以及右节点的右节点(如果存在)的表达式符号,并且输出计算结果。
  • 自定义栈,中缀表达式转换为后缀表达式并求值,三个抽象数据类型定义(1.class stack 2.class Middle_expressionToPost_expression 3.class Post_expression_value)
  • 08.中缀表达式转换后缀表达式算法.ppt
  • 文章目录题目AC代码 题目 本题链接:表达式求值 注:链接题目仅代表和本题大体相似 因为是考研笔试,本题代码以C语言去写 AC代码 代码解释: 代码:


    题目

    本题链接:表达式求值
    在这里插入图片描述

    考研对本知识点不要求写出实际代码,但必须掌握思路
    本题后续会补充C语言版本,其实就是模拟栈,关于栈的模拟,详见博客:数组模拟栈
    目前用C++中自带的STL函数

    下面分几个小点进行介绍:
    1.什么是中缀表达式以及后缀表达式
    2.中缀表达式转后缀表达式(思维)
    3.如何进行表达式求值

    1.什么是中缀表达式以及后缀表达式

    这个举栗子最容易理解:
    我们所熟知的计算方法其实就是中缀表达式,如:a + b, a - b, a * b ...
    大致概念就是两个数之间用运算符号链接,这就是中缀表达式,那么后缀表达式的概念是不是很容易猜到呢?
    a b +, a b -, a b * ...形如这种式子,就被称为后缀表达式,大概意思就是运算符在两个数之后。
    这里再举两个对应的中缀表达式和后缀表达式:
    中缀表达式:a + b - ca + b - c * d
    后缀表达式:a b + c -a b + c d * -
    其实从这里我们就可以看出,我们的中缀表达式转后缀表达式,数字的顺序(位置)其实是不会发生变化的,只有运算符的顺序(位置)才发生改变

    2.中缀表达式转后缀表达式(思维)

    这里还是举个栗子:
    中缀表达式:((15 / (7 - (1 + 1))) * 3 ) - (2 + (1 + 1))
    后缀表达式:15 7 1 1 + - / 3 * 2 1 1 + + -

    哈哈哈哈哈哈,是不是看着上面两个等价的前缀和中缀表达式一脸懵,下面讲解怎么把中缀表达式转为后缀表达式:
    1.确定中缀表达式中各个运算符的顺序
    2.选择下一个运算符,按照 [左操作数 右操作数 运算符] 的方式组合成一个新的操作数
    3.如果还有运算符没被处理就继续执行2.

    好了,看到这里,你愤怒了,这说了三点说了个啥?看球不懂啊!!!,这写的什么 ** 博客
    啊!客官莫急,且听我狡辩! 吓的博主赶紧拿出栗子去说明:
    这里我们拿一个基础的栗子:A + B * (C - D) - E / F
    我们来给这些符号编一个顺序,拿到上述的中缀表达式之后,我们按照小学思维去考虑:

    下面小故事的场景为一个班级中有一位老师(晶姐),两个学生:聪明的博主以及娇妹儿

    “同学们看这个表达式,我们应该最先去计算哪一个呀?“
    “小括号里面的元素!”(两个人异口同声的说到)
    “真聪明,所以我们先计算小括号中的 -,那么接下来呢?”

    这时,出现了两种不同的声音:
    “先算 *(博主吼道)
    “先算 /(娇妹儿吼道)

    两人俞吵俞烈,最后老师提出两个人打一架吧(不是
    最终,老师同意了 聪明的博主 的建议,先算*

    “那么接下来呢?”
    “先算 +(博主吼道)
    “先算 /(娇妹儿吼道)

    显然,博主说的是不容置疑的,故老师选择先计算+
    最后一步当然毋庸置疑的先计算/,最后计算-
    最终的后缀表达式被写成了:A B C D - * + E F / -

    大家可能要为娇妹儿打抱不平了,凭什么娇妹儿说的不对,难道知识因为娇妹儿比博主傻么!?
    确实(逃
    咳咳咳,其实娇妹儿说的不无道理,做法也是可取的,显然我们的后缀表达式也是可以按照娇妹儿的思维去写的,但是我们这里规定一个原则:左优先原则:只要左边的运算符能先计算,就优先算左边的

    为什么呢?
    1.计算机内部实现方式为左优先的原则去实现
    2.我们用左优先的原则写成后缀表达式之后,是非常直观的,读者可以再看一下我们上述过程中优先计算符号的顺序:- * + / -,恰好这种顺序正好是我们写成后缀表达式之后,后缀表达式中的顺序:A B C D - * + E F / -

    看到这里,读者应该明白如何进行中缀表达式以及后缀表达式之间的转换计算了,不妨看一下最开始的栗子,自己动手转换一下看看是否能转换成功

    3.如何进行表达式求值

    用栈实现后缀表达式的计算
    ①.从左往右扫描下一个元素,直到完全处理完所有的元素
    ②.若扫描到操作数则压入栈,并返回到①,否则执行③
    ③若扫描到运算符则弹出两个栈顶元素 (注:先出栈的为右操作数),执行相应操作,运算结果压回栈顶回到①

    若表达式合法,则最后栈中只会留下一个元素,就是最终结果

    AC代码

    注:考研中其实是不要求会写出下面的代码,但还是希望读者好好看懂并自己写一遍
    上面已经说的很详细了(自认为,咳咳),如果代码还有哪里不知道原因的话,可以评论或者私聊我,博主很闲,看到了就会及时回复的

    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <unordered_map>
    #include <stack>
    
    using namespace std;
    
    stack<char> op;
    stack<int> num;
    
    void eval()
    {
        auto b = num.top(); num.pop();
        auto a = num.top(); num.pop();
        auto c = op.top(); op.pop();
    
        int x;
        if (c == '+') x = a + b;
        else if (c == '-') x = a - b;
        else if (c == '*') x = a * b;
        else x = a / b;
        num.push(x);
    }
    
    int main()
    {
        string s;
        cin >> s;
    
        unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
        for (int i = 0; i < s.size(); i ++ )
        {
            if (isdigit(s[i]))
            {
                int j = i, x = 0;
                while (j < s.size() && isdigit(s[j]))
                    x = x * 10 + s[j ++ ] - '0';
                num.push(x);
                i = j - 1;
            }
            else if (s[i] == '(') op.push(s[i]);
            else if (s[i] == ')')
            {
                while (op.top() != '(') eval();
                op.pop();
            }
            else
            {
                while (op.size() && op.top() != '(' && pr[op.top()] >= pr[s[i]])
                    eval();
                op.push(s[i]);
            }
        }
    
        while (op.size()) eval();
        cout << num.top() << endl;
    
        return 0;
    }
    

    展开全文
  • 文章目录前缀表达式(波兰表达式)前缀表达式分析与介绍思路分析中缀表达式中缀表达式分析与介绍后缀表达式(逆波兰表达式)后缀表达式分析与介绍思路分析逆波兰计算器代码实现逆波兰计算器中缀表达式转换为后缀...
  • 本文实例为大家分享了C语言实现中缀表达式后缀表达式的具体代码,供大家参考,具体内容如下 中缀表达式转换为后缀表达式(思路) 1.创建栈 2.从左向右顺序获取中缀表达式 a.数字直接输出 b.运算符 情况一:遇到左...
  • 利用C语言实现中缀表达式转化为后缀表达式!!利用栈。
  • 一个算术表达式是由操作数(operand)、运算符(operator)和括号组成的。...用户可选择需要进行的操纵,包括后缀表达式的计算,中缀表达式转为后缀表达式,清屏和退出,界面清晰,操作简便,且有足够的输入合法性检验
  • 中缀表达式后缀表达式

    万次阅读 多人点赞 2019-04-12 17:55:21
    因为中缀表达式便于人们的理解与计算,但是后缀表达式更方便计算机的运算(如二叉树、堆栈的方法计算),因此在读取一个中缀表达式后,我们得办法将他转化为后缀表达式。 转化方式有三种: 首先假设我们需要转化.....

    自从找完工作人就废了,幡然醒悟不行不行,得把忘记的都记下来。。。。。。

    中缀表达式就是我们正常使用的那种,例如:a+b*c

    后缀表达式就是abc*+;

    为什么要有中缀表达式和后缀表达式呢?

    因为中缀表达式便于人们的理解与计算,但是后缀表达式更方便计算机的运算(如二叉树、堆栈的方法计算),因此在读取一个中缀表达式后,我们得办法将他转化为后缀表达式。

    转化方式有三种:

    首先假设我们需要转化的中缀表达式为:

    a + b * c + ( d * e + f ) * g

    第一种:基于堆栈的算法

    1. 从左到右扫描每一个字符。如果扫描到的字符是操作数(如a、b等),就直接输出这些操作数。

      c++堆栈的应用:中缀表达式转化为后缀表达式

    2. 如果扫描到的字符是一个操作符,分三种情况:

      (1)如果堆栈是空的,直接将操作符存储到堆栈中(push it)

      (2)如果该操作符的优先级大于堆栈出口的操作符,就直接将操作符存储到堆栈中(push it)

      (3)如果该操作符的优先级低于堆栈出口的操作符,就将堆栈出口的操作符导出(pop it), 直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中(push)。

      c++堆栈的应用:中缀表达式转化为后缀表达式

      c++堆栈的应用:中缀表达式转化为后缀表达式

    3. 如果遇到的操作符是左括号"(”,就直接将该操作符输出到堆栈当中。该操作符只有在遇到右括号“)”的时候移除。这是一个特殊符号该特殊处理。

      c++堆栈的应用:中缀表达式转化为后缀表达式

      c++堆栈的应用:中缀表达式转化为后缀表达式

      c++堆栈的应用:中缀表达式转化为后缀表达式

    4. 如果扫描到的操作符是右括号“)”,将堆栈中的操作符导出(pop)到output中输出,直到遇见左括号“(”。将堆栈中的左括号移出堆栈(pop )。继续扫描下一个字符

      c++堆栈的应用:中缀表达式转化为后缀表达式

    5. 如果输入的中缀表达式已经扫描完了,但是堆栈中仍然存在操作符的时候,我们应该讲堆栈中的操作符导出并输入到output 当中。

      c++堆栈的应用:中缀表达式转化为后缀表达式

      c++堆栈的应用:中缀表达式转化为后缀表达式

    第二种:括号法,这种真的很简单啊,好记又简单

          1:按照运算符的优先级对所有的运算单位加括号~

          式子变成拉:((a+(b*c))+(((d*e+f)*g))

           2:转换前缀与后缀表达式

          前缀:把运算符号移动到对应的括号前面

          则变成拉:++(a*(bc))*(+(*(de)f)g)

          把括号去掉:++a*bc*+*defg 前缀式子出现

          后缀:把运算符号移动到对应的括号后面

          则变成拉:((a(bc)*)+(((de)*f)+g)*)+

          把括号去掉:abc*+de*f+g *+后缀式子出现

    第三种:利用语法树

          1、将式子转化为二叉树,如下所示,图做的有点丑,懒得画了,不要介意。。。。。。

          2、通过后序遍历将其写出来,即可得到结果:abc*+de*f+g *+

    在这里补充一点,如何将表达式变成二叉树:

    表达式生成树的特点为:

        a. 叶子节点都是操作数;

        b. 非叶子节点都是运算符;

        c. 树根的运算符优先级低;

    步骤如下

    找到表达式中优先级最低的运算符作为树根(注意括号会提升内部的优先级),并将原表达式分解成左右两个表达式;

    分别对左右表达式做步骤1, 左边生成的树为树根的左子树,右边生成的树为树根的右子树;

    重复步骤1,2, 直到分解的表达式里没有运算符(只剩下数字)为止;

    注意一点:在遇到像本式中a后面的+号和c后面的+的优先级问题,在正常计算时a后面的+会先使用所以他的优先级比c后面的+优先级高。所以能得到上面的二叉树。

    后序遍历的问题看我其他的文章中有介绍。

    展开全文
  • 摘要:来实验室已经...在思考过程中发现,这个计算器的难点就是如何把中缀表达式转换为后缀表达式,以及如何计算后缀表达式。计算思路人的思路如果只是用于解题的话,这种方法是最快最准确的。但是它不适用于计算...

    摘要:来实验室已经两周了,用师兄的话说,基本处于自嗨状态。张老师问C++学的怎么样了?能不能编一个简单的计算器出来?我想这个计算器肯定不能简单到只算加减乘除,于是想来想去想写一个能处理括号的计算器,最好能写个简单的UI出来。在思考过程中发现,这个计算器的难点就是如何把中缀表达式转换为后缀表达式,以及如何计算后缀表达式。

    计算思路

    人的思路

    如果只是用于解题的话,这种方法是最快最准确的。但是它不适用于计算机。下面以a+b*c+(d*e+f)*g为例子讲以下人应该怎么把中缀表达式转换成后缀表达式。

    按先加减后乘除的原则给表达式加括号

    结果:((a+(b*c))+(((d*e)+f)*g))

    由内到外把每个括号里的表达式换成后缀

    最终结果:abc*+de*f+g*+

    这样就得到了中缀表达式转后缀表达式的最终结果。此法应付考试有神效。

    计算机的思路

    毕竟计算机跟人不一样,它“笨”啊!人的思路它用不了。那么它该怎么把中缀表达式转换成后缀表达式呢?

    计算机的思路需要用到栈,先来明确中缀表达式转后缀表达式的规则:

    1)如果遇到操作数,我们就直接将其输出。

    2)如果遇到操作符,则我们将其放入到栈中,遇到左括号时我们也将其放入栈中。

    3)如果遇到一个右括号,则将栈元素弹出,将弹出的操作符输出直到遇到左括号为止。注意,左括号只弹出并不输出。

    4)如果遇到任何其他的操作符,如(“+”, “”,“(”)*等,从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后,才将遇到的操作符压入到栈中。有一点需要注意,只有在遇到" ) "的情况下我们才弹出" ( ",其他情况我们都不会弹出" ( "。

    5)如果我们读到了输入的末尾,则将栈中所有元素依次弹出。

    下面以a+b*c+(d*e+f)*g为例子来讲讲计算机的转换过程。下面在描述栈的情况是直接用文字描述了,由左到右为栈底到栈顶。空表示栈空

    由左向右遍历表达式,首先遇到a,直接将其输出。

    此时输出为:a

    栈的情况为:空

    继续遍历,遇到+,将其放入栈中。

    此时输出为:a

    栈的情况为:+

    继续遍历,遇到b,直接将其输出。

    此时输出为:ab

    栈的情况为:+

    继续遍历,遇到*,因为*的优先级大于栈顶的+,所以将*放入栈内。

    此时输出为:ab

    栈的情况为:+*

    继续遍历,遇到c,直接将其输出。

    此时输出为:abc

    栈的情况为:+*

    继续遍历,遇到+,因为+的优先级低于栈顶的*,故将*弹出;然后新的栈顶元素的+与这个+优先级相同,故也要弹出现在栈顶的+;然后栈空了,将现在这个+放入栈中。

    此时输出为:abc*+

    栈的情况为:+

    继续遍历,遇到(,直接将其放入栈中,不遇到)不会将(弹出。

    此时输出为:abc*+

    栈的情况为:+(

    继续遍历,遇到d,直接将其输出。

    此时输出为:abc*+d

    栈的情况为:+(

    继续遍历,遇到*,因为栈顶为(,不遇到)不将(弹出,故直接将*放入栈中。

    此时输出为:abc*+d

    栈的情况为:+(*

    继续遍历,遇到e,直接将其输出。

    此时输出为:abc*+de

    栈的情况为:+(*

    继续遍历,遇到+,因为+比栈顶*的优先级低,故将*弹出;新的栈顶元素为(,不遇到)不弹出(,故将+放入栈中。

    此时输出为:abc*+de*

    栈的情况为:+(+

    继续遍历,遇到f,直接将其输出。

    此时输出为:abc*+de*f

    栈的情况为:+(+

    继续遍历,遇到),直接将栈中元素依次弹出并输出直到遇到(为止,注意:(弹出但不输出。

    此时输出为:abc*+de*f+

    栈的情况为:+

    继续遍历,遇到*,因为*的优先级大于栈顶元素+的优先级,故直接将*入栈。

    此时输出为:abc*+de*f+

    栈的情况为:+*

    继续遍历,遇到g,直接将其输出。

    此时输出为:abc*+de*f+g

    栈的情况为:+*

    继续遍历,为空,遍历结束。将栈内元素依次弹出。

    此时输出为:abc*+de*f+g*+

    栈的情况为:空

    至此,中缀表达式转后缀已经全部完成,结果为abc*+de*f+g*+。

    代码实现

    源代码

    代码是用C++写的,不过还是用的面向过程的思路。代码如下:

    //中缀表达式转后缀

    #include

    #include

    #include

    using namespace std;

    int prio(char op) { //给运算符优先级排序

    int priority;

    if (op == '*' || op == '/')

    priority = 2;

    if (op == '+' || op == '-')

    priority = 1;

    if (op == '(')

    priority = 0;

    return priority;

    }

    bool Trans(string &str,string &str1) { //引用传递

    stack s; //定义一个char类型的栈s

    int i;

    for (i = 0; i

    if (str[i] >= '0' && str[i] <= '9') { //如果是数字,直接入栈

    str1+=str[i];

    }

    else { //否则不是数字

    if (s.empty()) //栈空则入站

    s.push(str[i]);

    else if (str[i] == '(') //左括号入栈

    s.push(str[i]);

    else if (str[i] == ')') { //如果是右括号,只要栈顶不是左括号,就弹出并输出

    while (s.top() != '(') {

    str1+= s.top();

    s.pop();

    }

    s.pop(); //弹出左括号,但不输出

    }

    else {

    while (prio(str[i]) <= prio(s.top())) { //栈顶优先级大于等于当前运算符,则输出

    str1+= s.top();

    s.pop();

    if (s.empty()) //栈为空,停止

    break;

    }

    s.push(str[i]); //把当前运算符入栈

    }

    }

    }

    while (!s.empty()) { //最后,如果栈不空,则弹出所有元素并输出

    str1+= s.top();

    s.pop();

    }

    return true;

    }

    int main() { //主程序

    string infix;

    string postfix;

    cout << "请输入中缀表达式:" << infix << endl;

    cin >> infix;

    Trans(infix,postfix);

    cout << "后缀表达式为:" << postfix << endl;

    return 1;

    }

    程序测试

    这里我们就用a+b*c+(d*e+f)*g的实例1+2*3+(4*5+6)*7来测试我们的程序,可见运行结果为123*+45*6+7*+,计算正确。

    96eb65567ad9

    intopost.png

    总结

    在写这段小程序时有一些不小的收获。毕竟是一个初学者,犯的错误都是很低级的知识性错误,理解不到位,基础不扎实。这里要感谢我的本科同学白洋耐心地教我。

    1)string类的对象在没有初始化大小的情况下不要用其下标运算,会出现string subscript out of range(下标越界)的错误。在第三次执行循环时出现,大概是因为string对象的默认大小为2个字节。

    2)string类的对象不以'\0'结尾,要与C语言区分开来,判断其结束时用size()函数。size() 函数返回的是其大小,然后下标是以0开始的,所以最大到size-1。

    3)函数调用进行形实结合时要用引用传递。

    4)#include的使用。

    展开全文
  • c++使用堆栈实现中缀表达式后缀表达式
  • /*中缀表达式转成后缀表达式 "12+((22+31)*4)-5" ==> 12 22 31 + 4 * + 5 -第一步,将中缀表达式转成中缀字符串list,方便遍历 [12, +, (, (, 22, +, 31, ), *, 4, ), -, 5]第二步,将中缀字符串list转成后缀...

    /*

    中缀表达式转成后缀表达式 "12+((22+31)*4)-5" ==> 12 22 31 + 4 * + 5 -

    第一步,将中缀表达式转成中缀字符串list,方便遍历 [12, +, (, (, 22, +, 31, ), *, 4, ), -, 5]

    第二步,将中缀字符串list转成后缀表达式对应的list [12, +, (, (, 22, +, 31, ), *, 4, ), -, 5] -> [12, 22, 31, +, 4, *, +, 5, -]

    具体步骤:

    初始化两个栈,s1运算符栈,s2存储中间结果的栈

    遍历中缀表达式字符串list

    若是数字,直接入栈s2;

    若是"(",直接入栈s1;

    若是")",依次弹出符号栈s1的栈顶运算符,并入栈s2,直到遇到左括号,将左括号再出栈,把一对括号消除掉;

    若是操作符(加减乘除),比较它和s1栈顶操作符的优先级大小:

    a.若s1为空,或者栈顶运算符为"(",则直接将此运算符入栈;

    b.否则,若其优先级比栈顶运算符的优先级高,也将此运算符入栈;

    c.否则,将s1栈顶的运算符弹出,并入栈到s2中,继续从a循环。

    遍历结束后,把s1中剩余的运算符依次弹出,并加入s2。

    依次弹出s2中的元素,结果的逆序即为中缀表达式对应的后缀表达式。

    */

    public class InfixToPostfixDemo {

    // 第1步. 将中缀表达式转成中缀字符串列表,方便遍历。

    // "12+((22+31)*4)-5" ==> [12, +, (, (, 22, +, 31, ), *, 4, ), -, 5]

    public List toInfixList(String exp) {

    List res = new ArrayList<>();

    int i = 0;

    // 保存遍历过程中产生的数字,连续的数字字符拼接成一个数

    StringBuilder sb = new StringBuilder();

    while (i < exp.length()) {

    if (!Character.isDigit(exp.charAt(i))) {

    res.add(exp.charAt(i) + ""); // 如果当前字符不是数字,直接加入结果

    i++;

    } else {

    sb.delete(0, sb.length());// 先清除

    while (i < exp.length() && Character.isDigit(exp.charAt(i))) {

    sb.append(exp.charAt(i));

    i++;

    }

    res.add(sb.toString());

    }

    }

    return res;

    }

    // 第2步 将中缀表达式字符串列表,转成后缀表达式字符串列表.

    // [12, +, (, (, 22, +, 31, ), *, 4, ), -, 5] -> [12, 22, 31, +, 4, *, +, 5, -]

    public List toPostList(List list) {

    Stack s1 = new Stack<>(); // 符号栈

    // 存储中间结果

    List s2 = new ArrayList<>(); // 在整个转换过程中,没有pop操作,在后面还要逆序输出,所以用list代替栈

    for (String item : list) {

    if (item.matches("\\d+")) s2.add(item); // 如果是数字,加入s2

    else if (item.equals("(")) s1.push(item); // 如果是左括号,入栈s1

    else if (item.equals(")")) { // 如果是右括号,则依次弹出符号栈s1栈顶的运算符,并压入s2,直到遇到左括号位置,将这一对括号消除掉

    while (!s1.peek().equals("(")) {

    s2.add(s1.pop());

    }

    s1.pop(); // 丢弃左括号,继续循环,也就消除了一对括号

    } else { // 此时,遇到的是加减乘除运算符

    // 当前操作符优先级<=s1的栈顶运算符的优先级,则将s1的运算符弹出,并加入到s2中

    while (!s1.empty() && priority(s1.peek()) >= priority(item)) s2.add(s1.pop());

    s1.push(item);

    }

    }

    // 将s1中剩余的运算符依次弹出,并加入s2

    while (!s1.empty()) {

    s2.add(s1.pop());

    }

    return s2;

    }

    private int priority(String op) {

    if ("+".equals(op) || "-".equals(op)) return 1;

    if ("*".equals(op) || "/".equals(op)) return 2;

    return 0; // 如果是左括号返回0

    }

    // 对后缀表达式字符串列表进行计算

    public double calculatePoland(List list) {

    Stack stack = new Stack<>();

    for (String s : list) {

    double n1, n2;

    switch (s) {

    case "*":

    n1 = stack.pop();

    n2 = stack.pop();

    stack.push(n1 * n2);

    break;

    case "/":

    n1 = stack.pop();

    n2 = stack.pop();

    stack.push(n2 / n1);

    break;

    case "+":

    n1 = stack.pop();

    n2 = stack.pop();

    stack.push(n1 + n2);

    break;

    case "-":

    n1 = stack.pop();

    n2 = stack.pop();

    stack.push(n2 - n1);

    break;

    default:

    stack.push(Double.parseDouble(s));

    break;

    }

    }

    return stack.pop();

    }

    public static void main(String[] args) {

    String exp = "12+((22+31)*4)-5";

    InfixToPostfixDemo app = new InfixToPostfixDemo();

    List infixList = app.toInfixList(exp); // 第1步

    List postList = app.toPostList(infixList); // 第2步

    double res = app.calculatePoland(postList); //第3步

    System.out.println(infixList);

    System.out.println(postList);

    System.out.println(res);

    }

    }

    展开全文
  • 中缀表达式后缀表达式中缀表达式后缀表达式的规则。1.遇到操作数:直接输入到后缀表达式栈2.遇到运算符,直接入操作符栈3.遇到左括号:直接将其入栈4.遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈...
  • 中缀表达式后缀表达式并计算结果(c语言版)》由会员分享,可在线阅读,更多相关《中缀表达式后缀表达式并计算结果(c语言版)(8页珍藏版)》请在技术文库上搜索。1、中缀表达式后缀表达式中缀表达式后缀表达式...
  • 计算表达式,中缀表达式后缀表达式步骤详解以及代码实现(Java) 所谓的前、中、后缀表达式,简单阐述中缀表达式后缀表达式: **中缀表达式 *:常常人们书写的表达式就是中缀表达式,例如:4(1 + 2) - 3,就是...
  • 中缀表达式后缀表达式参考的文章就是直接给出了算法,但是算法如何推导出来的还没有弄明白,简单记录下我自己的理解,强行解释一下。后缀表达式就是操作符再操作数的后面,并且计算机能够根据简单的优先级就能进行...
  • 中缀后缀思想: 运算符的优先级: 运算符 级别(数字越大优先级越高) ( 1 +、- 2 *、/ 3 ) 4 扫描字符串,如果字符串是0~9的数字,添加到结果字符串中,如果是运算符,则进行一下判断:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,952
精华内容 7,180
关键字:

中缀表达式区别后缀表达式