首页 > 其他 > 详细

【中序式转后序式】

时间:2017-02-01 17:16:19      阅读:172      评论:0      收藏:0      [点我收藏+]
/*
中序式转后序式 
说明:
平常所使用的运算式,主要是将运算元放在运算子的两旁,例如a+b/d这样的式子,这称之为中序(Infix)表示式,对于人类来说,这样的式子很
容易理 解,但由于电脑执行指令时是有顺序的,遇到中序表示式时,无法直接进行运算,而必须进一步判断运算的先后顺序,所以必须将中序表示
式转换为另一种表示方 法。可以将中序表示式转换为后序(Postfix)表示式,后序表示式又称之为逆向波兰表示式(Reversepolish notation)
,它是由波兰的数学家卢卡谢维奇提出,例如(a+b)*(c+d)这个式子,表示为后序表示式时是ab+cd+*。
解法:
用手算的方式来计算后序式相当的简单,将运算子两旁的运算元依先后顺序全括号起来 ,然后将所有的右括号取代为左边最接近的运算子(从最内
层括号开始),最后去掉所有的左括号就可以完成后序表示式,
例如:a+b*d+c/d => ) ((a+(b*d))+(c/d)) > ->  bd*+cd/+
如果要用程式来进行中序转后序,则必须使用堆叠,演算法很简单,直接叙述的话就是使用回圈,取出中序式的字元,遇运算元直接输出,堆叠运
算子与左括号,ISP>ICP的话直接输出堆叠中的运算子,遇右括号输出堆叠中的运算子至左括号。
例如:(a+b)*(c+d)这个式子,依演算法的输出过程如下: 
OP        STACK        OUTPUT
(        (            -
a        (            a
+        (+            a
b        (+            ab
)        -            ab+
*        *            ab+
(        *(            ab+
c        *(            ab+c
+        *(+            ab+c
d        *(+            ab+cd
)        *            ab+cd+
-        -            ab+cd+* 
如果要将中序式转为前序式,则在读取中序式时是由后往前读取,而左右括号的处理方式相反 ,其余不变,但输出之前必须先置入堆叠,待转换
完成后再将堆叠中的 值由上往下读出,如此就是前序表示式。
*/


#include <stdio.h>
#include <stdlib.h>

int postfix(char* );
int priority(char );

int main(void)
{
    char input[80];
    
    printf("input infix: ");
    scanf("%s", input);
    postfix(input);
    
    return 0;
}

int postfix(char* infix)
{
    int i = 0, top = 0;
    char stack[80] = {\0};
    char op;
    
    while(1)
    {
        op = infix[i];
        
        switch(op)
        {
            case \0:
                while(top > 0)
                {
                    printf("%c", stack[top]);
                    top--;
                }
                printf("\n");
                return 0;
            case (:
                if(top < (sizeof(stack) / sizeof(char)))
                {
                    top++;
                    stack[top] = op;
                }
                break;
            case +:
            case -:
            case *:
            case /:
                while(priority(stack[top]) >= priority(op))
                {
                    printf("%c", stack[top]);
                    top--;
                }
                if(top < (sizeof(stack) / sizeof(char)))
                {
                    top++;
                    stack[top] = op;
                }
                break;
            case ):
                while(stack[top] != ()
                {
                    printf("%c", stack[top]);
                    top--;
                }
                top--;
                break;
            default:
                printf("%c", op);
                break;
        }
        i++;
    }
}

int priority(char op)
{
    int p;
    
    switch(op)
    {
        case +:
        case -:
            p = 1;
            break;
        case *:
        case /:
            p = 2;
            break;
        default:
            p = 0;
            break;
    }
    return p;
}

 

【中序式转后序式】

原文:http://www.cnblogs.com/libra-yong/p/6360114.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!