以前在大四升碩0的時後,因為太菜了,所以被老板要求寫這些資料結構程式當作練功,資料結構在研究所考試時是必考的,所以我以為我還算熟 , 但要實作程式出來又是另一回事了,可見在大學時真的背太多了 。最近整裡硬碟資料找到當初寫的code,所以在此做一下紀錄 。
主要是參考 Horowitz 資料結構聖經版
http://www.amazon.com/Fundamentals-Data-Structures-Ellis-Horowitz/dp/0929306406
這個中序轉後序程式可分為三個部份：
1. 運算元(A-Z ,0-9)與運算子( + - * / )的分離
- 使用isalnum()可以將數字/字母與符號分離
2. 堆疊的操作
- push() & pop()
3. 後序轉換演算法
- 在於比較運算子的優先權：左右括號 > 乘除 >加減
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#define STACK_SIZE 50
#define ADD_SUB 1 /* 代表 加減 */
#define MULT_DIV 2 /* 代表 乘除 */
#define LEFT 3 /* 代表左括號 */
#define RIGHT 4 /* 代表右括號 */
char stack[STACK_SIZE]; /* 堆疊陣列 */
int top=-1; /* 堆疊頂端指標 */
int priority[STACK_SIZE]; /*優先權堆疊 */
void push(char s,int number){
if(top>=STACK_SIZE-1){
printf("堆疊滿了");
}
else{
top++;
stack[top]=s;
priority[top]=number;
}
}
void pop(){
if (top==-1){
printf("堆疊已空\n");
}
else{
/*不要印出 '('*/
if( priority[top ]!=LEFT){
printf("%c",stack[top]);
}
top--;
}
}
/* 運算子處理 */
void Operator(char ch,int number) {
if(top==-1&&number!=RIGHT) /* 若堆疊為空 直接push */
push(ch,number);
else{
switch(number){
/* 若輸入為 ')' 從堆疊頂端依序pop直到出現'(' */
case RIGHT:
for(priority[top];priority[top]!=LEFT;pop()) ;
pop();//把最後的 '(' pop 但不印出
break;
/* 若輸入為 '(' 直接 PUSH */
case LEFT:
push(ch,number);
break;
/* 若輸入是 '+' '-' '*' '/' */
case ADD_SUB:
case MULT_DIV:
if( priority[top]==LEFT||priority[top]<number){
push(ch,number);
}
else{
/* 若堆疊內優先權 大於number */
while((priority[top]>=number)&&priority[top]!=LEFT)
pop(); /* 先POP 堆疊內再PUSH number */
push(ch,number);
}
break;
/*當字串已scan完 堆疊不為空 pop 剩下的運算子*/
case 0:
while(top!=-1)
pop();
break;
}
}
}
int main(void){
char *IndString;
char buf[STACK_SIZE];
int i=0;
int error_OP = 0;
printf("請輸入中序 :");
IndString=gets(buf);//中序輸入
printf("\n");
printf("後序為:");
/*若不等於結束字元*/
while(*(IndString+i)!='\0' & !error_OP) {
/*數字和字母是運算元所以直接印出 */
if(isalnum(*(IndString+i))) {
printf("%c",*(IndString+i));
}
else if(ispunct(*(IndString+i))) { //若不是數字 空白 字母 則為真
switch(*(IndString+i)){
case '+':
Operator(*(IndString+i),ADD_SUB);
break;
case '-':
Operator(*(IndString+i),ADD_SUB);
break;
case '*':
Operator(*(IndString+i),MULT_DIV);
break;
case '/':
Operator(*(IndString+i),MULT_DIV);
break;
case '(':
Operator(*(IndString+i),LEFT);
break;
case ')':
Operator(*(IndString+i),RIGHT);
break;
default:
printf(" error Operator\n");
error_OP = 1;
break;
}
}
i++;
}
Operator('\0',0);//字串scan結束
puts("\n------------------------------------\n");
return 0;
}
ps: 程式裡有使用到gets,通常建議改成fgets使用,不過懶得改了
執行結果：
