[C/C++] 中序轉前後序

1
#include
2
#include
3
#include
4

5
typedef struct Node{
6
    char value;
7
    Node* link;
8
}Node;
9

10
typedef struct Stack{
11
    Node* top;
12
}Stack;
13

14
void push(Stack* This, char ch){
15
    Node* newp = new Node{ch, This->top};
16
    This->top = newp;
17
}
18

19
char pop(Stack* This){
20
    char res;
21
    Node* temp = This->top;
22
    This->top = temp->link;
23
    res = temp->value;
24
    free(temp);
25
    return res;
26
}
27

28
char top(Stack* This){
29
    return (This->top == NULL)? '\0': This->top->value;
30
}
31

32
int empty(Stack* This){
33
    return (This->top == NULL)? true: false;
34
}
35

36
int priority(char x){
37
    switch(x){
38
        case '^':           return 3;
39
        case '*': case '/': return 2;
40
        case '+': case '-': return 1;
41
        default:            return 0;
42
    }
43
}
44

45
char* infixToPostfix(char str[100]){
46
    char ch, *rsl = (char*)malloc(sizeof(char) * 100);
47
    int idx = 0;
48
    Stack *stack = new Stack{NULL};
49
    for(int i = 0; i = priority(ch))
50
                    rsl[idx++] = pop(stack);
51
                push(stack, ch);
52
                break;
53
            default:
54
                rsl[idx++] = ch;
55
        }
56
    }
57
    //rest
58
    while(!empty(stack))
59
        rsl[idx++] = pop(stack);
60
    return &rsl[0];
61
}
62

63
char* infixToPrefix(char str[100]){
64
    char ch, *rsl = (char*)malloc(sizeof(char) * 100);
65
    int idx = 0;
66
    Stack *stack = new Stack{NULL};
67
    Stack *prefix = new Stack{NULL};
68
    for(int i = strlen(str)-1; i >= 0; i--){
69
        ch = str[i];
70
        //--------------------prefix--------------------
71
        switch(ch){
72
            case ')':
73
                push(stack, ch);
74
                break;
75
            case '(':
76
                while(!empty(stack) && (ch=pop(stack)) != ')')
77
                    push(prefix, ch);
78
                break;
79
            case '+': case '-': case '*': case '/': case '^':
80
                while(priority(top(stack)) > priority(ch))
81
                    push(prefix, pop(stack));
82
                push(stack, ch);
83
                break;
84
            default:
85
                push(prefix, ch);
86
        }
87
    }
88
    //rest
89
    while(!empty(stack))
90
        push(prefix, pop(stack));
91

92
    while(!empty(prefix))
93
        rsl[idx++] = pop(prefix);
94
    return rsl;
95
}
96

97
int main(void){
98
    char str[100];
99

100
    printf("請輸入中序運算式：");
101
    scanf(" %s", str);
102
    printf("後序: %s\n", infixToPostfix(str));
103
    printf("前序: %s\n", infixToPrefix(str));
104
    system("pause");
105
    return 0;
106
}