前言

This Series aritcles are all based on the book 《經典算法大全》; 對于該書的所有案例進行一個探究和拓展，并且用python和C++進行實現; 目的是熟悉常用算法過程中的技巧和邏輯拓展。

提出問題

22.Algorithm Gossip: 中序式轉后序式（前序式）

說明

平常所使用的運算式，主要是將運算元放在運算子的兩旁，例如a+b/d這樣的式子，這稱之為中序（Infix）表示式，對于人類來說，這樣的式子很容易理 解，但由于電腦執行指令時是有順序的，遇到中序表示式時，無法直接進行運算，而必須進一步判斷運算的先后順序，所以必須將中序表示式轉換為另一種表示方 法。可以將中序表示式轉換為后序（Postfix）表示式，后序表示式又稱之為逆向波蘭表示式（Reversepolish notation），它是由波蘭的數學家盧卡謝維奇提出，例如(a+b)(c+d)這個式子，表示為后序表示式時是ab+cd+。

解法

用手算的方式來計算后序式相當的簡單，將運算子兩旁的運算元依先后順序全括號起來 ，然后將所有的右括號取代為左邊最接近的運算子（從最內層括號開始），最后去掉所有的左括號就可以完成后序表示式。
如果要用程式來進行中序轉后序，則必須使用堆疊，演算法很簡單，直接敘述的話就是使用回圈，取出中序式的字元，遇運算元直接輸出，堆疊運算子與左括號， ISP>ICP的話直接輸出堆疊中的運算子，遇右括號輸出堆疊中的運算子至左括號。如果要將中序式轉為前序式，則在讀取中序式時是由后往前讀取，而左右括號的處理方式相反 ，其余不變，但輸出之前必須先置入堆疊，待轉換完成后再將堆疊中的 值由上往下讀出，如此就是前序表示式。

分析和解釋

代碼

C 代碼演示

#include <stdio.h> #include <stdlib.h> int postfix(char*); // 中序轉后序 int priority(char); // 決定運算子優先順序 int main(void) {char input[80];printf("輸入中序運算式：");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;}

拓展和關聯

后記

參考書籍

• 《經典算法大全》
• 維基百科

轉載于:https://www.cnblogs.com/actanble/p/6713394.html

總結

以上是生活随笔為你收集整理的Algorithm Gossip (22) 中序式转后序式（前序式）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。