## 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.

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*+

[ Data Structures with Java ] Section 14.5 : Infix Expression Evaluation

Algorithm Gossip: 中序式轉後序式（前序式）

### [ FP In Python ] Ch4. Higher-Order Functions

Preface   In the  last chapter  we saw an iterator algebra that builds on the  itertools  module. In some ways,  higher-order functions  (...