精华内容
下载资源
问答
  • 本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 题目:现有中缀表达式如:1+(2-3)*4+10/5 请用栈的特性编写一个程序,使得程序输出后缀表达式 分析如下: STEP1: 1+(2-3)...
  • 主要为大家详细介绍了C++实现中缀表达式转后缀表达式,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • (1) 从键盘或文件读入一个合法的算术表达式,输出相应的后缀表达式后缀表达式中,数据与数据之间加分隔符; (2) 输出正确的计算结果,保留两位小数点; (3) 考虑算法的健壮性,当表达式错误时,要给出错误...
  • NULL 博文链接:https://128kj.iteye.com/blog/1623312
  • 先写词法分析的源文件,用正则表达式表示出需要识别的字符,例如数字,乘法,加法和括号,如果识别到其他非法字符需要报错,用flex生成lex.yy.c文件。语法分析用LR方法进行语法分析,LR方法需要先根据文法构造自动机...
  • 中缀表达式转后缀表达式
  • 用dev c++写的代码,附有啰里啰嗦的注释和测试样例。太简单了不好意思要分。
  • 中缀表达式转换为后缀表达式(oj题库) 中缀表达式转换为后缀表达式(oj题库) 题目描述 中缀表达式是一个通用的算术或逻辑公式表示方法,操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的...
  • c语言实现中缀表达式转后缀表达式并求得计算结果,用顺序栈结构。 当输入者输入错误信息的时候需要报错,并说明错误的种类。
  • 文章目录题目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;
    }
    

    展开全文
  • 中缀表达式转后缀表达式,并进行计算; 支持: 支持函数: Abs 绝对值 Power 幂 Sqr 平方 Sqrt 平方根 Abs Sqr Sqrt 需要加括号 Power不需要 * 后缀运算符: * 第1级: () 从左到右 * 算出运算符: * 第4级:* \ % 从...
  • 摘要:来实验室已经...在思考过程中发现,这个计算器的难点就是如何把中缀表达式转换为后缀表达式,以及如何计算后缀表达式。计算思路人的思路如果只是用于解题的话,这种方法是最快最准确的。但是它不适用于计算...

    摘要:来实验室已经两周了,用师兄的话说,基本处于自嗨状态。张老师问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++中缀表达式转后缀表达式的具体代码,供大家参考,具体内容如下 1、初始化两个栈:运算符栈s1和储存中间结果的栈s2; 2、从左至右扫描中缀表达式; 3、遇到操作数时,将其压s2; 4、遇到...
  • c++使用堆栈实现中缀表达式转后缀表达式
  • midToLast():中缀表达式转后缀表达式 cal():后缀表达式计算结果 priority():计算符号优先级 GetList():将字符串切割存在队列里 中缀转后缀 首先传入一个队列存储的中缀表达式; 接着创建一个新队列,一个栈。 ...
    • 后缀表达式也叫逆波兰表达式。
    • 接下来将用后缀表达式实现复杂算术运算

    系统类:

    • midToLast():中缀表达式转后缀表达式
    • cal():后缀表达式计算结果
    • priority():计算符号优先级
    • GetList():将字符串切割存在队列里

    中缀转后缀

    首先传入一个队列存储的中缀表达式;
    接着创建一个新队列,一个栈。
    循环读取队列的字符:

    1. 如果是数字,压入新队列。
    2. 如果是左括号也直接压入新队列。
    3. 如果是运算符:
    4. ①如果栈为空或者栈顶为“(”或者当前运算符优先级大于栈顶运算符,入栈。
      ②否则,出栈,并将出栈元素压入新队列("("除外),一直到栈为空,或者遇到“(”或者当前元素大于栈顶元素;然后把当前元素压入栈。
    5. 如果是“)”,就出栈,并将出栈元素压入新队列;一直到遇到"(",把"("出栈但并不压入队列。
    6. 如果是其他符号就代表输入不符合规范。
    7. 最后把循环遍历完之后,把栈里面的元素全部压入队列,队列就是后缀表达式。

    后缀表达式计算结果

    创建一个栈,
    后缀表达式是从左往右扫描,循环遍历传入的后缀表达式。

    1. 如果字符是数字,压入栈。
    2. 如果是运算符,出栈两个数字进行运算。(后出栈那个作为被减数),然后将结果入栈。
    3. 循环完之后,栈中的元素就是运算结果。

    正则表达式

    正则表达式的好坏,决定了该程序的适用性。

    • . 匹配除换行符以外的任意字符。
    • [ ] 字符类,匹配方括号中包含的任意字符。
    • [^ ] 否定字符类。匹配方括号中不包含的任意字符
    • *匹配前面的子表达式零次或多次
    • +匹配前面的子表达式一次或多次
    • ? 匹配前面的子表达式零次或一次,或指明一个非贪婪限定符。
    • {n,m} 花括号,匹配前面字符至少 n 次,但是不超过 m 次。
    • (xyz) 字符组,按照确切的顺序匹配字符 xyz。
    • | 分支结构,匹配符号之前的字符或后面的字符。
    • \ 转义符,它可以还原元字符原来的含义,允许你匹配保留字符 [ ] ( ) { } . * + ? ^ $ \ |
    • ^ 匹配行的开始
    • $ 匹配行的结束

    源码

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    import java.util.Stack;
    
    public class demo1 {
        public static String cal(List<String> base) {//后缀表达式计算结果
            Stack<String> stack = new Stack<>();
            for (String item : base) {
                if (item.matches("[0-9]*[.]?[0-9]*")) {
                    stack.push(item);
                }else {
                    float result = 0;
                    if (item.equals("+")) {
                        float tem1 = Float.parseFloat(stack.pop());
                        float tem2 = Float.parseFloat(stack.pop());
                        result = tem2 + tem1;
                    } else if (item.equals("-")) {
                        float tem1 = Float.parseFloat(stack.pop());
                        float tem2 = Float.parseFloat(stack.pop());
                        result = tem2 - tem1;
                    } else if (item.equals("*")) {
                        float tem1 = Float.parseFloat(stack.pop());
                        float tem2 = Float.parseFloat(stack.pop());
                        result = tem2 * tem1;
                    } else if (item.equals("/")) {
                        float tem1 = Float.parseFloat(stack.pop());
                        float tem2 = Float.parseFloat(stack.pop());
                        result = tem2 / tem1;
                    } else if (item.equals("%")) {
                        float tem1 = Float.parseFloat(stack.pop());
                        float tem2 = Float.parseFloat(stack.pop());
                        result = tem2 % tem1;
                    } else {
                        throw new RuntimeException("有非法字符!");
                    }
                    stack.push("" + result);
                }
            }
            return stack.pop();
        }
    
        public static List GetList(String mes) {//将字符串分割成字符数组
            String[] strings = mes.split(" ");
            List<String> list = new ArrayList<String>();
            for (String item : strings) {
                list.add(item);
            }
            return list;
        }
    
        public static int priority(String item) {//计算符号优先级
            if (item.equals("+") || item.equals("-")) {
                return 1;
            } else {
                return 2;
            }
        }
    
        public static List midToLast(List<String> list) {//中缀转后缀
            Stack<String> stack = new Stack<>();
            List<String> newLists = new ArrayList<>();
            for (String item : list) {
                if (item.matches("[0-9]*[.]?[0-9]*")) {
                    while(item.startsWith("0")){
                        if(item.startsWith("0.")){
                            break;
                        }
                        item=item.substring(1);
                    }
                    newLists.add(item);
                } else if (item.equals("(")) {
                    stack.push(item);
                } else if (item.equals("+") || item.equals("-") || item.equals("*") || item.equals("/") || item.equals("%")) {
                    if (stack.empty() || priority(stack.peek()) < priority(item) || stack.peek().equals("(")) {
                        stack.push(item);
                    } else {
                        while (!stack.empty() && !stack.peek().equals("(")) {
                            if (priority(item) <= priority(stack.peek())) {
                                newLists.add(stack.pop());
                            }
                        }
                        stack.push(item);
                    }
                } else if (item.equals(")")) {
                    while (!stack.peek().equals("(")) {
                        newLists.add(stack.pop());
                    }
                    stack.pop();
                } else {
                    throw new RuntimeException("有非法字符!");
                }
            }
            while (!stack.empty()) {
                newLists.add(stack.pop());
            }
            return newLists;
        }
    
        public static void main(String[] args) {
            Scanner s = new Scanner(System.in);
            System.out.println("请输入中缀表达式:(每一个字符用空格隔开,目前支持的输入有数字,+-*/%,以及括号;退出请输入exit)");
            String mes = s.nextLine();
            while (!mes.equals("exit")) {
                String result = cal(midToLast(GetList(mes)));
                System.out.println("result:" + result);
                System.out.println("请输入中缀表达式:(每一个字符用空格隔开,目前支持的输入有数字,+-*/%,以及括号;退出请输入exit)");
                mes = s.nextLine();
            }
        }
    }
    
    
    

    图例

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    温馨提示:使用栈的peek()来进行比较的时候注意不要写出pop()。

    展开全文
  • 计算表达式,中缀表达式转后缀表达式步骤详解以及代码实现(Java) 所谓的前、中、后缀表达式,简单阐述中缀表达式后缀表达式: **中缀表达式 *:常常人们书写的表达式就是中缀表达式,例如:4(1 + 2) - 3,就是...

    计算表达式,中缀表达式转后缀表达式步骤详解以及代码实现(Java)

    所谓的前、中、后缀表达式,简单阐述中缀表达式和后缀表达式:

    • 中缀表达式:常常人们书写的表达式就是中缀表达式,例如:4*(1 + 2) - 3,就是我们平常所使用表达式,对于人来说,中缀表达式通俗易懂,知道怎样计算这个算式,容易理解计算步骤的优先级,那么对于计算机来说,怎样理解这个算式的优先级呢。(所谓优先级就是先计算小括号里的算式,再计算乘除后加减)
    • 后缀表达式:后缀表达式也称之为逆波兰表达式,若将上述例子的中缀表达式转换成后缀表达式可表示为:4 1 2 + * 3 -,对于计算机来说很容易理解后缀表达式的运算优先级,即从左到右先扫描到的操作符先运算,比如上述后缀表达式先执行 “+”,再执行 “*”,后执行 “-” 法运算。具体执行情况见下面计算后缀表达式步骤。

    中缀表达式转后缀表达式步骤

    1. 初始化两个栈:运算符栈s1和储存中间结果栈s2;

    2. 从左到右扫描中缀表达式;

    3. 遇到操作数时,将其压入s2;

    4. 遇到运算符时,比较其与s1栈顶运算符的优先级;

      4.1. 如果s1为空,或栈顶运算符为左括号“(”,则直接将此运算符入栈;

      4.2. 否则,若优先级比栈顶的运算符高,也将运算符压入s1;

      4.3. 否则(即优先级同级或者小),将s1栈顶的运算符弹出并压入s2中,再次转到4.1与新的栈顶运算符相比较;

    5. 遇到括号时;

    6. 重复2到5步骤,直到表达式的最右边;

    7. 将s1中剩余的运算符依次弹出并压入s2;

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

    举例说明

    假如中缀表达式为:1 + ((2 + 3)*4) - 5 转为后缀表达式为:1 2 3 + 4 * + 5 -

    扫描到的元素s1(栈底->栈顶)s2(栈底->栈顶)说明
    11扫描到数字直接压入s2栈
    ++1s1在这之前为空,直接压入元素+号
    (+ (1扫面到的元素为左括号则直接入s1栈
    (+ ( (1扫面到的元素为左括号则直接入s1栈
    2+ ( (1 2扫描到数字直接压入s2栈
    ++ ( ( +1 2栈顶为左括号,直接将扫描到的元素压入s1栈
    3+ ( ( +1 2 3数字 直接入s2栈
    )+ (1 2 3 +右括号,依次弹出s1栈顶元素并压入到s2栈中,
    直到遇到左括号,并丢弃该对括号
    *+ ( *1 2 3 +栈顶为左括号,直接压入元素
    4+ ( *1 2 3 + 4数字 直接压入s2栈
    )+1 2 3 + 4 *右括号,依次弹出s1栈顶元素并压入到s2栈中,
    直到遇到左括号,并丢弃该对括号
    --1 2 3 + 4 * +与栈顶比较 优先级不高于栈顶元素 则弹出栈顶元素至s2
    再与新的栈顶元素比较 栈顶为空 压入减号
    5-1 2 3 + 4 * + 5数字 直接压入s2栈
    扫描到达右端1 2 3 + 4 * + 5 -扫描到达右端后,将s1栈中剩余的元素依次弹出并压入到s2栈中

    中缀表达式转后缀表达式代码实现

    import java.util.*;
    
    /**使用方法:Stack<String> result = InfixPostExpression.switch(expression) 
    * expression:中缀表达式,字符串类型*/
    class InfixToPostExpression {
        
        /** 静态方法:以栈的形式返回后缀表达式 */
        public static Stack<String> switchList(String infixExpression) {
            // 字符串分割成数组
            // 遍历数组代替扫描表达式
            List<String> list = InfixToPostExpression.toList(infixExpression);
            System.out.println(list);
            Stack<String> numStack = new Stack<>();
            Stack<String> operateStack = new Stack<>();
            
            for (int i = 0; i < list.size();) {
                // 逐个取出列表中的元素
                String element = list.get(i);
                if (element.charAt(0) >= '0' && element.charAt(0) <= '9') {// 如果是数字直接压到numStack
                    numStack.push(element);
                    i++;
                }
                else if (operateStack.isEmpty()) {// 如果栈空直接将元素压入栈
                    operateStack.push(element);
                    i++;
                }
                else if (element.equals("+") || element.equals("-") || element.equals("*") || element.equals("/")) {// 如果为运算符 则比较优先级
                    if (operateStack.peek().equals("(") || operateStack.isEmpty()) {// 如果栈为空或者栈顶元素为左括号 则直接该元素压入operateStack栈中
                        operateStack.push(element);
                        i++;
                    }
                    // 如果当前运算符高于栈顶运算符 则直接将当前运算符压入operateStack栈中
                    else if ((element.equals("*") || element.equals("/")) && ((operateStack.peek().equals("+")) || (operateStack.peek().equals("-")))) {
                        operateStack.push(element);
                        i++;
                    }
                    else { // 否则 当前运算符优先级不大于栈顶运算符的优先级 则将栈顶运算符弹出压入到numStack栈中 再将当前运算符与下一个栈顶元素比较优先级 则i不递增
                        numStack.push(operateStack.pop());
                    }
                }
                else if (element.equals("(")){  // 如果当前元素为左括号 则直接压入operateStack栈中
                    operateStack.push(element);
                    i++;
                }
                else if (element.equals(")")) {  // 如果当前元素为右括号 依次将栈顶元素弹出压到numStack栈中 直到弹出元素为左括号 然后丢弃这一对括号
                    while (!(operateStack.peek().equals("("))) {
                        numStack.push(operateStack.pop());
                    }
                    operateStack.pop();
                    i++;
                }
            }
            
            // 当中缀表达式从左到右扫描完后 执行一下步骤
            // 把operateStack中剩余的元素弹出压到numStack栈中
            while (!operateStack.isEmpty()) {
                numStack.push(operateStack.pop());
            }
            
            // 再将numStack的元素顺序反转 即为后缀表达式
            while (!numStack.isEmpty()) {
                operateStack.push(numStack.pop());
            }
            
            return operateStack;
        }
        
        /** 静态方法:将字符串分割后返回List */
        public static List<String> toList(String str) {
            List<String> list = new ArrayList<>();
            
            String s = "";
            for (int i = 0; i < str.length(); i++) {
                // 如果是运算符 直接添加到列表中
                if ((str.charAt(i) >=  '9' || str.charAt(i) <= '0') && str.charAt(i) != ' ')
                    list.add(str.charAt(i) + "");
                else if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {  // 如果该字符是数字 需要处理是不是多位数
                    s += str.charAt(i);
                    // 如果字符串没有到达边界 且下一个字符也是数字就进行拼接
                    if (i + 1 >= str.length()  || str.charAt(i + 1) < '0' || str.charAt(i + 1) > '9') {
                       list.add(s);
                       s = "";
                    }
                }   
            }
            
            return list;
        }
    }
    

    转换得到后缀表达式,对于写程序来计算后缀表达式相当简单,以下为具体的就算过程:

    计算后缀表达式步骤

    • 创建一个栈储存中间的计算结果,假如栈名为 stack
    • 从左至右扫描后缀表达式
      • 若为数字,将数字压入到stack栈中
      • 若为运算符,依次弹出栈顶两个数字进行响应的运算,将运算结果压入stack栈中
    • 直到扫描完后缀表达式,最后stack栈中只剩一个数,即为计算结果

    举例说明

    以上述后缀表达式为例:1 2 3 + 4 * + 5 -

    扫描到的元素stack栈中的动态示意说明
    11数字直接入栈
    21 2数字直接入栈
    31 2 3数字直接入栈
    +1 5弹出3、2 ,将2 + 3结果压入栈中
    41 5 4数字直接入栈
    *1 20弹出5,4, 将4 * 5结果压入栈中
    +21弹出20,1,将1 + 20结果压入栈中
    521 5数字直接入栈
    -16弹出5,21 将21 - 5结果压入栈中

    扫描后缀表达式到达右端后,satck栈中只剩一个元素为16,即最后栈中的元素为计算后缀表达式的结果

    计算后缀表达式的代码实现

    import java.util.*;
    
    /** 计算后缀表达式 */
    public class CalculateWithPostExpression {
        
        public double culculate(String str) {
            // 将中缀表达书转换成后缀表达式
            Stack<String> stack = InfixToPostExpression.switchList(str);
            Stack<Number> numberStack = new Stack<>();
            
            // 根据后缀表达式的计算步骤计算
            // 1.从左到右扫描后缀表达式 
            // 2.若为数字就压入栈中 
            // 3.若为操作符则依次弹出两个栈顶元素进行响应的运算,将运算结果压入栈中
            // 4.扫描结束后 栈中仅剩的一个元素即为表达式的计算结果
            int count = stack.size();
            for (int i = 0; i < count; i++) {
                // 如果为数字直接压栈
                if (stack.peek().charAt(0) >= '0' && stack.peek().charAt(0) <= '9') {
                    numberStack.push(Double.valueOf(stack.pop()));
                }
                else {  // 否则 进行相应的操作
                    double num1 = (double)numberStack.pop();  // 弹出栈顶的数字
                    double num2 = (double)numberStack.pop();
                    switch (stack.pop()) {  // 进行相应的运算
                        case "+" : numberStack.push(num2 + num1);break;
                        case "-" : numberStack.push(num2 - num1);break;
                        case "*" : numberStack.push(num2 * num1);break;
                        case "/" : numberStack.push(num2 / num1);break;
                        default : throw new RuntimeException("输入的表达有误");
                    }         
                }
            }
            
            return (double)numberStack.pop();  // 返回栈中最后一个元素,即为计算结果
        }
    }
    

    总结

    想要计算机以人们的预期来理解中缀表达式的优先级,然后计算中缀表达式,此举并不简单,但是计算后缀表达式对于写程序来实现先对简单。但是难点在于中缀表达式转换成后缀表达式,当然,如果觉得转换过程麻烦,或者不理解亦或看不懂实现转换的代码,也有直接计算中缀表达式的方法,以及代码实现,等我更新。。。

    展开全文
  • 中缀表达式转后缀表达式参考的文章就是直接给出了算法,但是算法如何推导出来的还没有弄明白,简单记录下我自己的理解,强行解释一下。后缀表达式就是操作符再操作数的后面,并且计算机能够根据简单的优先级就能进行...
  • 本文使用实现了MATLAB实现中缀表达式转后缀表达式并计算(数字包含0-9,符号包含+-*、())后缀表达式得到结果,下面是原理和代码。代码可以在CSDN中下载。
  • 中缀表达式转后缀表达式并计算结果(c语言版)》由会员分享,可在线阅读,更多相关《中缀表达式转后缀表达式并计算结果(c语言版)(8页珍藏版)》请在技术文库上搜索。1、中缀表达式转后缀表达式中缀表达式转后缀表达式...

空空如也

空空如也

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

中缀表达式转后缀表达式

友情链接: 6369990.rar