基本原理是一樣的，都是順序掃描中綴表達(dá)式，用一個(gè)操作符棧進(jìn)行中間處理。
牽涉運(yùn)算符優(yōu)先級(jí)。
過(guò)去是按照是操作符還是操作數(shù)處理，對(duì)于操作符做比較混亂的邏輯判斷。
這里分別對(duì)操作數(shù)，加減乘除左括號(hào)右括號(hào)進(jìn)行分別處理，邏輯更簡(jiǎn)單。
程序的邏輯結(jié)構(gòu)在于分解。
1 // 中綴轉(zhuǎn)后綴
2 // 原汁原味
3
4 #include <stdio.h>
5 #include <string.h>
6 #include <stdlib.h>
7 #define MAX 100
8
9 char* infixToPostfix(char postfix[], char infix[])
10 {
11 static char stack[MAX];
12 int top = 0, ch, i = 0, j = 0;
13 ch = infix[i++];
14 while (ch != '#')
15 {
16 switch (ch)
17 {
18 case '(':
19 stack[top++] = ch;
20 break;
21 case ')':
22 while (top > 0 && stack[top - 1] != '(')
23 {
24 postfix[j++] = stack[--top];
25 }
26 --top;
27 break;
28 case '+':
29 case '-':
30 while (top > 0 && stack[top - 1] != '(')
31 {
32 postfix[j++] = stack[--top];
33 }
34 stack[top++] = ch;
35 break;
36 case '*':
37 case '/':
38 while (top > 0 && (stack[top - 1] == '*' || stack[top - 1] == '/'))
39 {
40 postfix[j++] = stack[--top];
41 }
42 stack[top++] = ch;
43 break;
44 case ' ':
45 break;
46 default:
47 postfix[j++] = ch;
48 }
49 ch = infix[i++];
50 }
51 while (top > 0)
52 {
53 postfix[j++] = stack[--top];
54 }
55 postfix[j++] = '\0';
56 return postfix;
57 }
58
59 int main()
60 {
61 char infix[MAX];
62 char stack[MAX];
63 char postfix[MAX];
64
65 scanf("%s", infix);
66 infixToPostfix(postfix, infix);
67 printf("%s\n", infix);
68 printf("%s\n", postfix);
69 return 0;
70 }
posted on 2011-06-30 20:36
unixfy 閱讀(144)
評(píng)論(0) 編輯 收藏 引用