设为首页 加入收藏

TOP

逆波兰表达式 - 中缀表达式转后缀表达式(一)
2019-08-13 05:39:32 】 浏览:44
Tags:波兰 表达式 后缀

先说一下中缀表达式,平时我们使用的运算表达式就是中缀表达式,例如1+3*2,中缀表达式的特点就是:二元运算符总是置于与之相关的两个运算对象之间


人读起来比较好理解,但是计算机处理起来就很麻烦,运算顺序往往因表达式的内容而定,不具规律性



 


后缀表达式,后缀表达式的特点就是:每一运算符都置于其运算对象之后,以上面的中缀表达式1+2*3为例子,转为后缀表达式就是123*+



 


下面先分析怎么把中缀表达式转换为后缀表达式,这里我们考虑六种操作符'+'、'-'、'*'、'/'、'('、')',完成中缀转后缀我们需要两个数组,都以栈的方式来操作,一个数组用来存放后缀表达式(char num[100]),


一个数组用来临时存放操作数(char opera[100])(这里说临时存放,是因为最后都要入栈到后缀表达式数组num中,这个数组就相当于一个中转站)


 


1、从左往右扫描中缀表达式(这里我们以1*(2+3)为例)



 


2、如果是数字那么将其直接入栈到数组num


3、如果是操作数,需要进一步判断


(1)如果是左括号'('直接入栈到数组opera


(2)如果是运算符('+'、'-'、'*'、'/'),先判断数组opera栈顶的操作数的优先级(如果是空栈那么直接入栈到数组opera),如果是左括号那么直接入栈到数组opera中,如果栈顶是运算符,且栈顶运算符的优先级大于该运算符


那么将栈顶的运算符出栈,并入栈到数组num中,重复步骤3,如果栈顶运算符优先级小于该运算符,那么直接将该运算符入栈到opera中


(3)如果是右括号')',那么说明在opera数组中一定有一个左括号与之对应(在你没输错的情况下),那么将opera中的运算符依次出栈,并入栈到num中,直到遇到左括号'('(注意左括号不用入栈到num


4、如果中缀表达式扫描完了,那么将opera中的操作数依次出栈,并入栈到num中就可以了,如果没有没有扫描完重复1-3步


上面就是中缀表达式转后缀表达式的步骤了,下面用图来直观的了解一下这个过程


 












需要注意的是:opera中操作数,越靠近栈顶,优先级越高,下面附上实现代码


void PexpretoSexpre(char *ss)
{
    char num[100] = "0";    /* 存储后缀表达式 */
    char opera[100] = "0";    /* 存储运算符 */
    /*
    num----j
    opera----op
    ss----i
    */
    int i, j, op;


    op = i = j = 0;


    while (ss[i] != '\0')
    {
        if (isdigit(ss[i]))    /* 如果是数字 */
        {
            num[j] = ss[i];    /* 数字直接入后缀表达式栈 */
            j++;
            i++;
        }
        else
        {
            switch (ss[i])    /* 如果是操作数 */
            {
            case '+':
                {
                    if (op == 0)    /* 如果是空栈 */
                    {
                        PushOperation(opera, ss, &op, &i);    /* 入运算符栈 */
                        break;
                    }
                    if (opera[op-1] == '+' || opera[op-1] == '-' || opera[op-1] == '*' || opera[op-1] == '/' || opera[op-1] == ')' || opera[op-1] == '(')
                    {
                        switch (opera[op-1])
                        {
                        case '+':
                            {
                                PushOperation(opera, ss, &op, &i);
                                break;
        &n
编程开发网

首页 上一页 1 2 3 4 5 6 7 下一页 尾页 1/8/8
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Java集合 LinkedList的原理及使用 下一篇C语言编码方式之ASCII、ANSI、Uni..