精华内容
参与话题
问答
  • 后缀表达式是计算机容易运算的表达式,运算符在运算数后面,从左到右进行运算,无需考虑优先级,运算呈线性结构. 先举个简单的转换例子 2+9/3-5 (前缀)-> 2 9 3 / + 5 - (后缀) 先进行乘除再进行加减 运算规律,.....

    中缀转后缀
    本文大部分资料参考慕课何钦铭老师的数据结构
    相关的慕课链接:表达式求值
    中缀表达式是最常用的算术表达式,运算符在运算数中间,运算需要考虑运算符优先级.
    后缀表达式是计算机容易运算的表达式,运算符在运算数后面,从左到右进行运算,无需考虑优先级,运算呈线性结构.
    先举个简单的转换例子
    2+9/3-5 (前缀)-> 2 9 3 / + 5 - (后缀)
    先进行乘除再进行加减
    运算规律,运算数位置不变,改变的是运算符位置
    可以推栈实现,用堆栈储存等待中的运算符.
    将当前运算符与最后一个等待的运算符比较.

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

    再来解释一下开始的简单例子
    在这里插入图片描述
    括号的运算
    在这里插入图片描述
    选取慕课里何钦铭老师的案例
    在这里插入图片描述
    后缀表达式运算步骤:
    (以堆栈储存)
    从左到右,遇到运算符就弹出相应的运算数,运算后再把结果入栈.最终结果就是栈顶数的值.
    (由于该运算为线性结构,具体运算时是不需要储存输出后的运算符,一般是输出一个运算符就进行一次运算,不像图中要储存输出状态.)
    注意点:
    有时候’-’(负号)是单目运算符,则要修改运算数.
    遇到其他运算符(如幂运算)也类似.

    这篇文章只是整理中缀表达式转后缀表达式的方法和理论,目的是为了理解.
    具体代码实现看我的另一篇文章(模拟表达式运算).
    这部分转换对于初学者来说可能很模糊,建议去看开头链接的那个视频.
    如果有什么错误或不足欢迎评论指出.

    展开全文
  • 后缀表达式

    万次阅读 多人点赞 2018-06-21 22:27:12
    后缀表达式:9 3 1-3*+ 10 2/+规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。下面是详细的步骤:1. 初始化一...

    后缀表达式:9 3 1-3*+ 10 2/+

    • 规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈,进行运算,运算结果进栈,一直到最终获得结果。

    下面是详细的步骤:

    1. 初始化一个空。此桟用来对要运算的数字进出使用。

    2. 后缀表达式中前三个都是数字,所以9、3、1进栈。

    3. 接下来是减号“-”,所以将栈中的1出栈作为减数,3出栈作为被减数,并运算3-1得到2,再将2进栈。

    4. 接着是数字3进栈。

    5. 后面是乘法“*”,也就意味着栈中3和2出栈,2与3相乘,得到6,并将6进栈。

    6. 下面是加法“+”,所以找中6和9出找,9与6相加,得到15,将15进栈。

    7. 接着是10与2两数字进栈。

    8. 接下来是符号因此,栈顶的2与10出栈,10与2相除,得到5,将5进栈。

    9. 最后一个是符号“+”,所以15与5出找并相加,得到20,将20进栈。

    10. 结果是20出栈,栈变为空。


     后缀表达式又称逆波兰表达式,明显的特点是:逆波兰表达式中没有括号,计算时将操作符之前的第一个数作为右操作数,第二个数作为左操作数,进行计算,得到的值继续放入逆波兰表达式中。 
       但日常生活中我们总是习惯于写中缀表达式,所以需要先将中缀表达式转为后缀表达式。 
       假如中缀表达式为:12*(3+4)-6+8/2 
       在遇到数字时,我们直接输出,遇到符号,则入栈。但在入栈时,我们要判断栈内已有的操作符的优先级和需要判断的操作符的优先级的大小。 
       栈内<栈外:入栈操作符 
       栈内>栈外:出栈操作符 
       栈内=栈外:出栈 栈内的操作符并入栈 栈外的操作, 
       遇到 ‘(’:直接入栈 
       遇到 ‘)’:出栈所有操作符直达遇到 ‘(’ 
       因为第一个操作符进入时也需要比较,所以在创建出保存操作符的栈时,直接就入栈一个’#’,别的字符也行,只要是非操作符就行,并将其优先级设为”1”,其他操作设为更低的”-1”。 
       优先级: 
       0–>’#’; 
       1–>’(‘; 
       2–>’+’; 
       2–>’-‘; 
       3–>’*’; 
       3–>’/’; 
       4–>’)’; 
       其他情况下优先级均为’-1’。但是我们在判断优先级时,因为’(‘的优先级为’1’,比较小,所以判断时要先判断是否为’(‘,是的话直接入栈,我们可以用if,else if,else完成。 
       具体代码实现如下: 
      

    
    #include <iostream>
    #include <stack>
    #include <math.h>
    using namespace std;
    
    bool Number(char ch)//判断是否为数字,是则返回true
    {
        if (ch >= 48 && ch <= 57)
            return true;
        else
            return false;
    }
    
    void InPut(char*& str)//接收输入的中缀表达式的函数,并简单判断是否合法
    {
        cout << "Please Enter What You Want To calculation:" << endl;
        while (1)
        {
            cin >> str;
    
            if (Number(str[0]))//中缀表达式的第一个必定是数字,如果不是,则非法
            {
                break; 
            }
            else
            {
                cout << "Illegal Input,Please Input Again:";
                delete[] str;
            }
        }
    }
    
    int GetPriority(char sy)//设置各个操作符的优先级
    {
        switch (sy)
        {
        case '#':
            return 0;
        case '(':
            return 1;
        case '+':
        case '-':
            return 3;
        case '*':
        case '/':
            return 5;
        case ')':
            return 6;
        default:
            return -1;
        }
    }
    
    
    void AddSpace(char*& arr)//给转成的后缀表达式的数字和符号添加空格,区分每个字符
    {
        *arr = ' ';
        arr++;
    }
    
    char* GetBack()//获取后缀表达式的函数
    {
        char* middle = new char[30];
        char* back = new char[30];
        char* backend = back;
        InPut(middle);
        stack<char> s;
        s.push('#');
        while (*middle)
        {
            if (Number(*middle) || *middle == '.')//如果是数字或者小数的话,直接输出
            {
                *back = *middle;
                back++, middle++;
            }
            else
            {
                if (Number(*(back - 1)))//只有他的上一个时数字的话,才继续给空格
                                        //否则遇到多个操作符,则输出域会存在多个空格
                {
                    //*back = ' ';
                    //back++;
                    AddSpace(back);
                }
                if (*middle == ')')//如果右括号的话,输出所有操作符直到遇到左括号,并抛弃相对应的一堆括号
                {
                    while (s.top() != '(')
                    {
                        *back = s.top();
                        s.pop();
                        back++;
                        AddSpace(back);
                    }
                    middle++;
                    s.pop();//抛弃左括号
                }
                else if (*middle == '(')//遇到左括号,则进入栈
                {
                    s.push(*middle); middle++;
                }
                else if (GetPriority(*middle) > GetPriority(s.top()))//如果栈内的操作符优先级高于栈外的优先级,则入栈
                {
                    s.push(*middle); middle++;
                }
                else if (GetPriority(*middle) <= GetPriority(s.top()))
                                                         //如果栈内的操作符优先级低于或等于栈外的优先级,输出栈内的符号,并入栈栈外的符号
                {
                    *back = s.top();
                    s.pop(); 
                    s.push(*middle);
                    back++; middle++;
                    AddSpace(back);
                }
            }
        }
        while (s.top() != '#')//中缀表达式遍历完成,但是=栈中还有符号存在,一一出栈输出
        {
            AddSpace(back);
            *back = s.top();
            s.pop(); back++;
        }
        *back = '\0';
        cout << "The Back Is: " << backend << endl;
        return backend;
    }
    
    double GetNumber(char*& arr)
    {
        //因为输出为char*,所以可能两位数以上的数字被拆开,此函数为正确得到数字
        double sum[10] = { 0 }; int i = 0; double result = 0;
        while (*arr != ' ')
        {
            sum[i] = *arr-48;
            i++;
            arr++;
        }
        int k = i - 1;
        for (int j = 0; j < i; j++,k--)
        {
            result += (sum[j] * pow(10, k));
        }
        return result;
    }
    
    double Cauculate(char ch, double left, double right)//各个操作符对应的操作
    {
        switch (ch)
        {
        case '+':
            return left + right;
        case '-':
            return left - right;
        case '*':
            return left * right;
        case '/':
            return left / right;
        default:
            return 0;
            break;
        }
    }
    
    double CountBack(char* back)
    {
        stack<double> s;
        while (*back)
        {
            if (Number(*back))//遇到数字
            {
                s.push(GetNumber(back));//将正确的数字入栈
            }
            else if (*back == ' ')
            {
                back++;//遇到空格跳过
            }
            else
            {
                double a = s.top();
                s.pop();
                double b = s.top();
                s.pop();
                s.push(Cauculate(*back, b, a));//遇到符号时,取栈顶的第二个数和第一个数求解,并入栈
                back++;
            }
        }
        while (s.size() >= 2)//最终栈内存在的数大于2时,继续计算,直到只剩下一个数
        {
            double a = s.top();
            s.pop();
            double b = s.top();
            s.pop();
            s.push(Cauculate(*back, b, a));
        }
        //返回这个数字,既是最终结果
        return s.top();
    }
    
    void FunTest()
    {
        cout << "The Result Is: " <<CountBack(GetBack()) << endl;
    }
    
    int main()
    {
        FunTest();
        system("pause");
        return 0;
    }


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

    万次阅读 多人点赞 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后面的+优先级高。所以能得到上面的二叉树。

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

     

     

     

    展开全文
  • 中缀表达式转换为后缀表达式

    万次阅读 多人点赞 2012-09-20 21:34:02
    一、后缀表达式求值 后缀表达式也叫逆波兰表达式,其求值过程可以用到栈来辅助存储。假定待求值的后缀表达式为:6 5 2 3 + 8 * + 3 + *,则其求值过程如下: 1)遍历表达式,遇到的数字首先放入栈中,此时栈...

    在回复中说明不够清晰,在这里说明下,本文第一部分摘自《数据结构和算法分析-C语言描述》一书,只是做了一些概括和总结。


    一、后缀表达式求值

    后缀表达式也叫逆波兰表达式,其求值过程可以用到栈来辅助存储。假定待求值的后缀表达式为:6  5  2  3  + 8 * + 3  +  *,则其求值过程如下:

    1)遍历表达式,遇到的数字首先放入栈中,此时栈如下所示:

    2)接着读到“+”,则弹出3和2,执行3+2,计算结果等于5,并将5压入到栈中。

    3)读到8,将其直接放入栈中。

    4)读到“*”,弹出8和5,执行8*5,并将结果40压入栈中。而后过程类似,读到“+”,将40和5弹出,将40+5的结果45压入栈...以此类推。最后求的值288。

     

     

    二、中缀表达式转后缀表达式

    2.1)规则

    中缀表达式a + b*c + (d * e + f) * g,其转换成后缀表达式则为a b c * + d e * f  + g * +。

    转换过程需要用到栈,具体过程如下:

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

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

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

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

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

     

    2.2)实例

    规则很多,还是用实例比较容易说清楚整个过程。以上面的转换为例,输入为a + b * c + (d * e + f)*g,处理过程如下:

    1)首先读到a,直接输出。

    2)读到“+”,将其放入到栈中。

    3)读到b,直接输出。

    此时栈和输出的情况如下:

     

    4)读到“*”,因为栈顶元素"+"优先级比" * " 低,所以将" * "直接压入栈中。

    5)读到c,直接输出。

    此时栈和输出情况如下:

     

    6)读到" + ",因为栈顶元素" * "的优先级比它高,所以弹出" * "并输出, 同理,栈中下一个元素" + "优先级与读到的操作符" + "一样,所以也要弹出并输出。然后再将读到的" + "压入栈中。

    此时栈和输出情况如下:

     

    7)下一个读到的为"(",它优先级最高,所以直接放入到栈中。

    8)读到d,将其直接输出。

    此时栈和输出情况如下:

     

    9)读到" * ",由于只有遇到" ) "的时候左括号"("才会弹出,所以" * "直接压入栈中。

    10)读到e,直接输出。

    此时栈和输出情况如下:

     

    11)读到" + ",弹出" * "并输出,然后将"+"压入栈中。

    12)读到f,直接输出。

    此时栈和输出情况:

     

     

    13)接下来读到“)”,则直接将栈中元素弹出并输出直到遇到"("为止。这里右括号前只有一个操作符"+"被弹出并输出。

     

    14)读到" * ",压入栈中。读到g,直接输出。

     

    15)此时输入数据已经读到末尾,栈中还有两个操作符“*”和" + ",直接弹出并输出。

    至此整个转换过程完成。程序实现代码后续再补充了。

     

     2.3)转换的另一种方法

    1)先按照运算符的优先级对中缀表达式加括号,变成( ( a+(b*c) ) + ( ((d*e)+f) *g ) )

    2)将运算符移到括号的后面,变成((a(bc)*)+(((de)*f)+g)*)+

    3)去掉括号,得到abc*+de*f+g*+

    展开全文
  • 中缀表达式转换为后缀表达式(C语言代码+详解)

    万次阅读 多人点赞 2019-01-22 14:53:22
    中缀表达式转换为后缀表达式 1.创建栈 2.从左向右顺序获取中缀表达式 a.数字直接输出 b.运算符 情况一:遇到左括号直接入栈,遇到右括号将栈中左括号之后入栈的运算符全部弹栈输出,同时左括号出栈但是不输出。...
  • 前缀、中缀、后缀表达式

    万次阅读 多人点赞 2011-09-09 14:54:38
    关键字:概念, 前缀表达式, 前缀记法, 中缀表达式, 中缀记法, 波兰式, 后缀表达式, 后缀记法, 逆波兰式 它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与...
  • 表达式树与前中后缀表达式

    千次阅读 多人点赞 2018-10-11 21:09:03
    计算机科学中,除了栈以外,二叉树也是处理表达式的常用工具,为了处理表达式而遵循相应规则构造的树被称为表达式树。 表达式树 算数表达式是分层的递归结构,一个运算符作用于相应的运算对象,其运算对象又可以是...
  • 详解如何将中缀表达式转化为后缀表达式

    万次阅读 多人点赞 2018-04-14 17:49:53
    本文我将从两种角度来解析如何将中缀表达式转化为后缀表达式一、从应对考试角度来(在最快的时间内得出最准确的答案)首先我们应该知道,要想将中缀转化为后缀,需要借助堆栈实现。(不准备画图了,画图有点浪费时间...
  • 一、前言  通常我们把栈归为一种基本的数据结构,同时它也是一种线性表结构,也就是说你要自己实现一个栈的数据结构,既可以用数组实现,也可以用链表实现。栈最主要的特点就是“先进后出”,因为栈只有一个入口和...
  • 中缀表达式转后缀表达式 12+8-25/3-6*(5+3) 12 8 + 25 3 / - 6 5 3 + * - 中缀表达式字符串从左至右, 若遇到运算数,则直接将数字输出 若遇到运算符 +-*/ ,则与栈顶元素比较,若是该运算符优先级高于栈顶...
  • 题目:前缀表达式和后缀表达式的文法分别为:前e->*(e.e)|+(e.e)|a后e->(e.e)*|(e.e)+|a编一个程序。输入一个前缀表达式,输出一个与之等价的后缀表达式:假设输入的前缀表达式没有语法错误。例如:输入+(*(a,+...
  • C++后缀表达式

    千次阅读 2018-06-08 18:12:05
    1 基本概念后缀表示法也叫逆波兰表示法(前缀就是波兰表示法),由于所有的操作符都在操作数的后面,所以被称为后缀表示法。中缀表示法的操作符在操作数之间,也是最符合人的逻辑。...后缀表达式:512+4*+3-2 中缀...
  • 关于后缀表达式的计算机求值以及中缀表达式转后缀表达式的分析请看我的另一篇博客——中缀表达式转前、后缀表达式及其求值后缀表达式求值#include<iostream> #include #include #include<cctype> #include using ...
  • 中缀表达式转后缀表达式求值

    千次阅读 2019-03-27 17:29:59
    刚开始想一鼓作气把整个过程全部实现,但白费了那几个小时,调试了半天也没做出来,后来我是通过先实现中缀表达式转化为后缀表达式,然后实现后缀表达式的求值,然后将两块代码进行合成,刚才同学还笑着说:模块化...
  • 后缀表达式

    千次阅读 2019-04-04 16:04:05
    P1060 欢迎进入@shuai:开心的金明; 题目描述 金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你...
  • 1.中缀表达式转换成后缀表达式: 首先需要注意的是:中缀转后缀的结果并不唯一。例如:(a+b+c*d)/e是一个中缀表达式,ab+cd*+e/与abcd*++e/都是其后缀表达式。 转换方式:先根据中缀表达式的各操作符的优先级,...
  • 使用堆栈计算后缀表达式

    千次阅读 2019-01-29 16:01:18
    使用堆栈计算后缀表达式 一、实现栈结构 根据栈的先进后出的特点,很容易设置栈结构的接口:入栈、出栈、判空、size()等。可以用线性表的方法来实现一个栈结构,其实也就两种,用链表或数组实现栈。 但是,在C++...
  •  输入一个只包含加减乖除和括号的合法表达式,求表达式的值。其中除表示整除 输入格式  输入一行,包含一个表达式 输出格式  输出这个表达式的值 样例输入 1-2+3*(4-5) 样例输出 -4 数据规模和约定  ...
  • 因为数据结构老师布置了栈的后缀表达式实验,经过思考,有以下反思。 中缀表达式转换为后缀表达式 关于括号,直接将括号里面的符号加入后缀表达式。 关于数字,直接推入后缀表达式 遇到±符号,如果栈为空或者栈顶...
  • 后缀表达式的计算 后缀表达式: 指的是不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行。(不再考虑运算符的优先规则)。 中缀表达式: 也就是我们日常最容易见到...

空空如也

1 2 3 4 5 ... 20
收藏数 116,691
精华内容 46,676
关键字:

unigui 允许下载文件 后缀