程式扎記: [C 範例代碼] Infix to Postfix translation (Recursive approach)

標籤

2013年2月22日 星期五

[C 範例代碼] Infix to Postfix translation (Recursive approach)


前言:
Infix 是人類使用的算術表示方法, 下面是 Wiki 對 Infix notation 的說明:
Infix notation is the common arithmetic and logical formula notation, in which operators are written infix-style between the operands they act on (e.g. 2 + 2). It is not as simple to parse by computers as prefix notation ( e.g. + 2 2 ) or postfix notation ( e.g. 2 2 + ), but many programming languages use it due to its familiarity.

問題在於電腦程式要解析 Infix 的表示式有一定的困難度, 因此存在了 Infix -> Postfix 的轉換. 因為相對 Infix 來說, Postfix 對電腦程式來說容易解析.

範例代碼:
下面代碼為 C 語言的 Infix->Postfix 轉換範例代碼:
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>   
  4.   
  5. #define bool int  
  6. #define true 1  
  7. #define false 0  
  8.   
  9. char operators[] = "+-*/^";  
  10.   
  11. struct Stk_Chr  
  12. {  
  13.     int pt;  
  14.     char buffer[256];  
  15. } Stack_Chr;  
  16.   
  17. int Stack_Chr_Size(struct Stk_Chr *pstack)  
  18. {  
  19.     return pstack->pt;  
  20. }  
  21.   
  22. void Stack_Chr_Init(struct Stk_Chr *pstack)  
  23. {  
  24.     pstack->pt =0;  
  25.     memset(pstack->buffer,0,sizeof(char)*256);  
  26. }  
  27.   
  28. bool Stack_Chr_Is_Empty(struct Stk_Chr *pstack)  
  29. {  
  30.     if(pstack->pt ==0)  
  31.         return true;  
  32.     return false;  
  33. }  
  34.   
  35. bool Stack_Chr_Is_Full(struct Stk_Chr *pstack)  
  36. {  
  37.     if(pstack->pt >=255)  
  38.         return true;  
  39.     return false;  
  40. }  
  41.   
  42. bool Stack_Chr_Push(struct Stk_Chr *pstack, char data)  
  43. {  
  44.     if(Stack_Chr_Is_Full(pstack))  
  45.         return false;  
  46.     pstack->buffer[pstack->pt] = data;  
  47.     pstack->pt++;  
  48.     return true;  
  49. }  
  50.   
  51. bool Stack_Chr_Pop(struct Stk_Chr *pstack, char *data)  
  52. {  
  53.     if(Stack_Chr_Is_Empty(pstack))  
  54.         return false;  
  55.     pstack->pt--;  
  56.     *data = pstack->buffer[pstack->pt];  
  57.   
  58.     return true;  
  59. }  
  60.   
  61. bool Stack_Chr_PopOut(struct Stk_Chr *pstack)  
  62. {  
  63.     if(Stack_Chr_Is_Empty(pstack))  
  64.         return false;  
  65.     pstack->pt--;  
  66.   
  67.     return true;  
  68. }  
  69.   
  70. bool Stack_Chr_Peer(struct Stk_Chr *pstack, char *data)  
  71. {  
  72.     if(Stack_Chr_Is_Empty(pstack))  
  73.         return false;  
  74.     *data = pstack->buffer[(pstack->pt)-1];  
  75.     return true;  
  76. }  
  77.   
  78. bool isOperator(char op)  
  79. {  
  80.     char *pch;  
  81.     pch = strchr(operators, op);  
  82.     if(pch!=NULL)  
  83.     {  
  84.         return true;  
  85.     }  
  86.     else  
  87.     {  
  88.         return false;  
  89.     }  
  90. }  
  91.   
  92. bool isSubexpr(char op)  
  93. {  
  94.     if(op == '('return true;  
  95.     return false;  
  96. }  
  97.   
  98. int priority(char op)  
  99. {  
  100.   switch(op) {  
  101.   case '+'case '-'return 1;  
  102.   case '*'case '/'return 2;  
  103.   default:            return 0;  
  104.   }  
  105. }  
  106.   
  107. char* InfixToPostfix(char* infixExp, char* opostfixExp, int s, int e)  
  108. {  
  109.     int i, j, k, idx=0;  
  110.     struct Stk_Chr stack;   
  111.     Stack_Chr_Init(&stack);  
  112.   
  113.     char tchr;  
  114.     char *postfixExpr = (char*)malloc(100*sizeof(char));  
  115.     for(i=s; i
  116.     {  
  117.         if(infixExp[i]== ' 'continue;  
  118.         else if(isOperator(infixExp[i]))  
  119.         {  
  120.             if(Stack_Chr_Is_Empty(&stack)==1)  
  121.             {  
  122.                 Stack_Chr_Push(&stack, infixExp[i]);  
  123.             }  
  124.             else  
  125.             {  
  126.                 Stack_Chr_Peer(&stack, &tchr);  
  127.                 if(priority(infixExp[i]) > priority(tchr))  
  128.                 {  
  129.                     Stack_Chr_Push(&stack, infixExp[i]);  
  130.                 }  
  131.                 else  
  132.                 {  
  133.                     postfixExpr[idx] = tchr;  
  134.                     Stack_Chr_PopOut(&stack);  
  135.                     idx+=1;  
  136.                     Stack_Chr_Push(&stack, infixExp[i]);  
  137.                 }  
  138.             }  
  139.         }  
  140.         else if(isSubexpr(infixExp[i]))  
  141.         {  
  142.             int cnt = 1;  
  143.             int si = i+1;  
  144.             char ichr;  
  145.             while(cnt > 0 && si < strlen(infixExp))  
  146.             {  
  147.                 ichr = infixExp[si];  
  148.                 if(ichr == '(') cnt++;  
  149.                 else if(ichr==')') cnt--;  
  150.                 si++;  
  151.             }  
  152.             if(cnt == 0)  
  153.             {  
  154.                 si--;  
  155.                 InfixToPostfix(infixExp, postfixExpr, i+1, si);  
  156.                 idx = strlen(postfixExpr);  
  157.                 i = si;  
  158.             }  
  159.             else  
  160.             {  
  161.                 printf("Illegal infix expression!\n");  
  162.                 return;  
  163.             }  
  164.         }  
  165.         else  
  166.         {  
  167.             postfixExpr[idx]=infixExp[i];  
  168.             idx++;  
  169.         }  
  170.     }  
  171.     while(Stack_Chr_Is_Empty(&stack)==0)  
  172.     {  
  173.         Stack_Chr_Pop(&stack, &tchr);  
  174.         postfixExpr[idx] = tchr;  
  175.         idx++;  
  176.     }  
  177.     strcat(opostfixExp, postfixExpr);  
  178.     free(postfixExpr);  
  179.     return opostfixExp;  
  180. }  
  181.   
  182. int main()  
  183. {  
  184.     int i, j, k, idx=0;  
  185.     char expr[100];  
  186.     char *postfixExpr = (char*)malloc(100*sizeof(char));;  
  187.     memset(postfixExpr,0,sizeof(char)*100);  
  188.     printf("Give Infix expression: ");  
  189.     scanf("%s", expr);  
  190.     InfixToPostfix(expr, postfixExpr, 0, strlen(expr));  
  191.     printf("\t[Info] Postfix=%s\n", postfixExpr);  
  192.     free(postfixExpr)
  193.     return 0;  
  194. }  
執行結果:
Give Infix expression: a*(b+c)+d*e
[Info] Postfix=abc+*de*+

上面再 stdin 輸入 Infix 表示式 "a*(b+c)+d*e" 得到的 Postfix 表示式為 "abc+*de*+". 有關 Java 版本的 Infix->Postfix 轉換可以參考:
[ Data Structures with Java ] Section 14.5 : Infix Expression Evaluation

補充說明:
Algorithm Gossip: 中序式轉後序式(前序式)
平常所使用的運算式,主要是將運算元放在運算子的兩旁,例如a+b/d這樣的式子,這稱之為中序(Infix)表示式,對於人類來說,這樣的式子很容易理 解,但由於電腦執行指令時是有順序的,遇到中序表示式時,無法直接進行運算,而必須進一步判斷運算的先後順序,所以必須將中序表示式轉換為另一種表示方 法...


沒有留言:

張貼留言

網誌存檔