基本原理是一样的，都是顺序扫描中缀表达式，用一个操作符栈进行中间处理。
牵涉运算符优先级。
过去是按照是操作符还是操作数处理，对于操作符做比较混乱的逻辑判断。
这里分别对操作数，加减乘除左括号右括号进行分别处理，逻辑更简单。
程序的逻辑结构在于分解。
1 // 中缀转后缀
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 阅读(129)
评论(0) 编辑 收藏 引用