[C/C++ 演算法]-資料結構與演算法(文魁)：中序表示法轉後序表示法之演算法(1)

 

線上執行結果：http://www.tutorialspoint.com/compile_c_online.php

code2html：http://tohtml.com/

 

 

/* =============== Program Description =============== */
/* 程式名稱 : 7_3_3.cpp								   */
/* 程式目的 : 中序表示法轉後序表示法之演算法	       */
/* 輸    入 : 中序表示法的字串陣列資料				   */
/* 輸    出 : 前序表示法的字串陣列資料		           */
/* =================================================== */
#define n 12
// 宣告標頭檔
#include "stdio.h"
// 宣告全域變數
char Stack[n];
int top=-1;
// 宣告函式原型
// 利用傳址的方式把Array A傳進parsing2函式中
void parsing2(char *A);
int isOperand(char ch);    /* 判斷��否為運算元 */
int isEmpty(void);        /* 判斷堆疊��否為空 */
int isFull(void);          /* 判斷堆疊��否滿了 */
char pop(void);          /* 由堆疊取出資料 */
void push(char ch);       /* 將資料放入堆疊 */
int priority(char op);      /* 判斷運算符號優先順序 */
void main(void)
{
char A[n]="1+2*(3-4)/2";
// 轉換前的資料
printf(" Data before parsing : %s\n",A);
printf("\n");
parsing2(A);
// 轉換後的資料
printf(" Data after parsing : %s\n",A);
printf("\n");
getchar();
}
void parsing2(char *A)
{
int i,j=0,m=0;
char ch,ch1;
char B[n];
for(i=n-2;i>=0;i--)
{
ch = A[i];
if(isOperand(ch))
B[j++]=ch;
else
{
if(ch==')')
{
m++;
push(ch);
}else if(ch=='(')
{
m++;
while(!isEmpty())
{
ch = pop();
if(ch==')')
break;
else
B[j++] = ch;
}
}else{
if(!isEmpty())
{
do
{
ch1 = pop();
if(priority(ch1)>priority(ch))
{
B[j++] = ch1;
if(isEmpty())
{
push(ch);
break;
}
}
else{
push(ch1);
push(ch);
break;
}
}while(!isEmpty());
}else{
push(ch);
}
}
}
}
while(!isEmpty())
B[j++] = pop();
for(i=0;i<n-1-m;i++)
A[n-2-m-i]=B[i];
A[n-1-m]='\0';
}
int isOperand(char ch)
{
int ret;
switch(ch)
{
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
ret = 0;
break;
default:
ret = 1;
break;
}
return ret;
}
int isEmpty(void)
{
if(top==-1)
return 1;
else
return 0;
}
int isFull(void)
{
if(top==n-1)
return 1;
else
return 0;
}
char pop(void)
{
char ch = Stack[top];
Stack[top] = 0;
top--;
return ch;
}
void push(char ch)
{
Stack[++top]=ch;
}
int priority(char op)
{
int p;
switch(op) {
case '+': case '-':
p = 1;
break;
case '*': case '/':
p = 2;
break;
        default:
p = 0;
break;
}
return p;
}