精华内容
下载资源
问答
  • 中缀表达式转后缀表达式

    万次阅读 多人点赞 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)+g))

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

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

          则变成拉:((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后面的+优先级高。所以能得到上面的二叉树。

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

     

     

     

    展开全文
  • 中缀表达式转后缀表达式的方法

    万次阅读 多人点赞 2020-08-03 22:13:54
    表达式求值: 1.从左到右进行遍历 2.运算数,直接输出. 3.左括号,直接压入堆栈,(括号是最高优先级,无需比较)(入栈后优先级降到最低,确保其他符号正常入栈) 4.右括号,(意味着括号已结束)不断弹出栈顶运算符并输出直到...

    表达式求值:

    1.从左到右进行遍历
    2.运算数,直接输出.
    3.左括号,直接压入堆栈,(括号是最高优先级,无需比较)(入栈后优先级降到最低,确保其他符号正常入栈)
    4.右括号,(意味着括号已结束)不断弹出栈顶运算符并输出直到遇到左括号(弹出但不输出)
    5.运算符,将该运算符与栈顶运算符进行比较,
    如果优先级高于栈顶运算符则压入堆栈(该部分运算还不能进行),
    如果优先级低于等于栈顶运算符则将栈顶运算符弹出并输出,然后比较新的栈顶运算符.
    (低于弹出意味着前面部分可以运算,先输出的一定是高优先级运算符,等于弹出是因为同等优先级,从左到右运算)
    直到优先级大于栈顶运算符或者栈空,再将该运算符入栈.
    6.如果对象处理完毕,则按顺序弹出并输出栈中所有运算符.

    如何将中缀转后缀思路: 假如表达式是一个字符串

    创建一个符号栈和一个字符串队列

    遍历各个字符信息

    判断该字符是 运算符、括号、数值

    • 运算符

      判断当前字符优先级是否小于等于栈顶字符优先级,此时栈顶元素中的左括号(,优先级最小

      • 小于等于 将符号栈栈顶内容弹出且存入到字符串队列中,将当前字符存入到符号栈中
      • 大于将当前字符存入到符号栈中
    • 括号

      • 左括号存入到符号栈中
      • 右括号 依次将符号栈中的运算符弹出进入到字符串队列中直到在符号栈中弹出出现左括号停止弹栈 数值 直接进入到字符串队列中
    • 数值

      直接输出

    遍历结束后 判断符号栈中是否有元素

    #include <iostream>
    #include <algorithm>
    #include <queue>
    #include <set>
    #include <stack>
    #include <string>
    #include <vector>
    #include <string.h>
    #include <stdio.h>
    #include <stdlib.h>
    #include <math.h>
    using namespace std;
    #define MAX 1000
    char *change(char data[]);
    bool compare(char a, char b);
    int priority(char a);
    // (40  括号在算术上优先级最高,但是在 栈的优先级是最低的,为了其他符号正常入栈 优先级最低
    //  /* 优先级最高 , +- 优先级最低
    
    // true 的情况 只有a 是*/ b是+-的情况
    int priority(char a)
    {
        if (a == '(')
        {
            return 0;
        }
        else if (a == '+' || a == '-')
        {
            return 1;
        }
        else
        {
            return 2;
        }
    }
    // 比较优先级 ,a 的优先级比b 高,就返回true
    bool compare(char a, char b)
    {
        return priority(a) > priority(b);
    }
    // 中缀表达式--> 后缀表达式(逆波兰表达式)
    // 返回字符串数组
    char *change(char data[])
    {
    
        char *hou = (char *)malloc(MAX * sizeof(char));
        stack<char> s;
        int index = 0; // 后缀表达式的长度
        int length = strlen(data);
        // 1. 判断类型
        for (int i = 0; i < length; i++)
        {
            // 如果是运算数,直接输出,
            if (data[i] >= '0' && data[i] <= '9')
            {
                hou[index] = data[i];
                index++;
            }
            else if (data[i] == ')')
            {
                // 不断的弹出栈元素并输出直到遇到左括号结束
                while (!s.empty() && s.top() != '(')
                {
                    hou[index] = s.top();
                    index++;
                    s.pop();
                }
                s.pop(); //退出左括号
            }else if(data[i]=='('){
                 s.push(data[i]);
            }
            else
            {
                // 表示 运算符优先级小于等于 栈顶元素,就退出栈顶元素,并输出
                // 包含情况data[i]='(',compare 返回false
                
                while (!s.empty() && !compare(data[i], s.top()))
                {
                    printf("%c %c %d\n",data[i],s.top(),compare(data[i], s.top()));
                    hou[index] = s.top();
                    index++;
                    s.pop();
                }
                s.push(data[i]);
            }
            printf("此时输出内容 %-20s \t参加运算的符号 %c  \t\t栈的元素个数%d \n", hou, data[i], s.size());
        }
    
        // 输出栈内所有元素
        while (!s.empty())
        {
            hou[index] = s.top();
            index++;
            s.pop();
        }
        return hou;
    }
    
    // 后缀表达式的计算
    int main(int argc, char const *argv[])
    {
        // 样例 2*(9+6/3-5)+4
        // 结果 2963/+5-*4+
        char s[MAX] = "2*2*2*2+2";
        char *result;
        result = change(s);
        printf("%s\n", result);
        return 0;
    }
    
    

    在这里插入图片描述

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,045
精华内容 1,618
关键字:

中缀表达式转后缀表达式