中缀后缀互相转换_76350543201611217525565分析

1、中缀后缀互相转换符号说明 为了表示简便，程序中符号如下 , 非 v,或 , 与 , 推出 =, 等价中缀转后缀将中缀表达式转换为后缀将中缀表达式转换为后缀表达式表达式 (1) 初始化两个栈：运算符栈S1和储存中间结果的队列S2； (2) 从左至右扫描中缀表达式； (3) 遇到操作数时，将其压入S2； (4) 遇到运算符时，比较其与S1栈顶运算符的优先级： (4-1) 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈； (4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1 （注意转换为前缀表达式时是优先级较高或相同，而这里则 不包括相同的情况）； (4-3) 否则，将S1

2、栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；中缀转后缀 (5) 遇到括号时： (5-1) 如果是左括号“(”，则直接压入S1； (5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃； (6) 重复步骤(2)至(5)，直到表达式的最右边； (7) 将S1中剩余的运算符依次弹出并压入S2； (8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。中缀转后缀 例1 PvQ(R=T) 输出：PQRT= v扫描到的元素S1(栈底-栈顶)S2(队头-队尾)说明

3、P空P命题符号，直接入队列vvPS1为空，运算符直接入栈QvPQ命题符号，直接入队列vPQv优先级小于，运算符直接入栈(v(PQ左括号直接入栈S1Rv(PQR命题符号，直接入队列=v(“=”PQRS1栈顶是左括号，直接入栈Tv(“=”PQRT命题符号，直接入队列)vPQRT=右括号，弹出运算符直至遇到左括号到达最右端空PQRT=vS1中剩余的运算符中缀转后缀 例2 (Pv(QvR)v(SvT) 输出: PQRvvSTvv 扫描到的元素扫描到的元素S1(栈底栈底-栈顶栈顶)S2(队头队头-队尾队尾)说明说明(空左括号直接入栈S1P(P命题符号，直接入队列v(vPS1栈顶是左括号，直接入栈(v(P

4、左括号直接入栈S1Q(v(PQ命题符号，直接入队列v(v(vPQS1栈顶是左括号，直接入栈R(v(vPQR命题符号，直接入队列)(vPQRv右括号，弹出运算符直至遇到左括号)空PQRvv右括号，弹出运算符直至遇到左括号vvPQRvvS1为空，运算符直接入栈(v(PQRvv左括号直接入栈S1Sv(PQRvvS命题符号，直接入队列vv(vPQRvvSS1栈顶是左括号，直接入栈Tv(vPQRvvST命题符号，直接入队列)vPQRvvSTv右括号，弹出运算符直至遇到左括号达到最右端空PQRvvSTvvS1中剩余的运算符后缀转中缀将后缀表达式转换为前缀表达式，遵循以下步骤： 定义类型Expr，Expr类

5、型的变量表示一个表达式，它有两个属性： Expr.e，表示表达式的字符串 Expr.o，将表达式转化为后缀表达时，最右侧的运算符 将输入的表达式每一个变量和运算符都转化为Expr变量，e属性即为变量或者运算符的字符，运算符的o属性就是它本身。 处理之后的表达式为 e1 e2 e3 . en后缀转中缀 1）从左向右扫描 2）当ei为运算符时，考察它左侧的两个变量ei-2和ei-1: 如果ei-1.o的优先级小于ei.o，则ei-1的表达式左右加括号，即ei-1.e = (ei-1.e) 对ei-2进行同样判断 将三者合并为新的Expr变量s，其中s s.e = ei-2.e ei.e ei-1.e s.o = ei.o 3）最后一个变量扫描完毕之后，整个序列只剩下一个Expr变量e，其e属性即为我们需要的中缀表示。后缀转中缀 例1 PQRT= 输出：PQ(R=T)扫描位置坐标扫描位置坐标公式公式0P Q R T = 1P Q R T = 2P Q R T = 3P Q R T = 4P Q R T = 3P Q R=T 2P Q(R=T) PQ(R=T)后缀转中缀 例2 PQRST 输出: (P(QR)(ST)扫描位置坐标扫描位置坐标公式公式0P Q R S T 1P Q