-
Notifications
You must be signed in to change notification settings - Fork 0
/
系統程式期末
137 lines (125 loc) · 2.29 KB
/
系統程式期末
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <stdio.h>
#include <stdlib.h>
#define N 50
#define OP 5
char op[OP] = {'(','+','-','*','/',};
int op_priority[OP] = {0,1,1,2,2};//與op[OP]對應,用以存放運算子的優先順序
int priority(char c);
void to_postfix(char infix[], char postfix[]);
char stack[N];
int top=-1;
// 將資料 item 放入堆疊
void push(char item){
if (top>=N-1){
printf("Stack full!\n");
exit(-1);
}
stack[++top]=item;
}
// 傳回堆疊頂端的資料,但並非取出
int pop(){
if (top==-1){
printf("Stack empty!\n");
exit(-1);
}
return stack[top--];
}
void stackPrint(){
int i;
printf("stack =");
for (i=0; i<=top; i++)
printf(" %c", stack[i]);
printf("\n");
}
// 判斷是否為空堆疊
bool IsEmpty(void)
{
return (top < 0) ? true : false;
}
// 判斷堆疊是否滿溢
bool IsFull()
{
return (top >= N - 1) ? true : false;
}
// 傳回堆疊頂端的資料
char top_data()
{
return stack[top];
}
// 傳回運算子 c 的優先序
int priority(char c)
{
int i;
for( i=0; i < OP; i++)
if(op[i] == c)
return op_priority[i];
return -1;
}
// 將中置式infix轉成後置式postfix
void to_postfix(char infix[], char postfix[])
{
int i=0, j=-1;
char x, y;
while((x=infix[i++]) != '\0'){
switch(x){
case '(' : push(x);
break;
case ')' : while(! IsEmpty() && (x=pop()) != '(')
postfix[++j]=x;
break;
case '+' :
case '-' :
case '*' :
case '/' : y=top_data();
while(priority(y) >= priority(x)){
postfix[++j]=pop();
y=top_data();
}
push(x);
break;
default :
postfix[++j]=x;
}
}
while(! IsEmpty())
postfix[++j]=pop();
postfix[++j]='\0';
}
bool IsDight(char c)
{
return c>='0' && c<='9';
}
int calculate(char postfix[])
{
int point=0;
while(postfix[point]!='\0')
{
while(IsDight(postfix[point]))
push(postfix[point++]);
int a=pop()-'0', b=pop()-'0',c=0;
switch(postfix[point])
{
case'+':c=b+a;
break;
case'-':c=b-a;
break;
case'*':c=b*a;
break;
case'/':c=b/a;
break;
}
push(c+'0');
point++;
}
return pop()-'0';
}
int main(void)
{
char infix[50], postfix[50];
printf("請輸入運算式: ") ;
scanf("%s",infix);
to_postfix(infix,postfix);
printf("\n\n中序式 : %s \t後序式 : %s\n",infix , postfix);
printf("答案: %d\n", calculate(postfix));
return 0;
}