討論區快速選單
知識庫快速選單
討論區最近新進100則主題 下載Alexa Toolbar讓你上網更有趣 我的IT職涯該如何規劃 ?
[ 回上頁 ] [ 討論區發言規則 ]
中序轉前序
更改我的閱讀文章字型大小
作者 : x2163126(吃冬瓜補西瓜)
[ 貼文 38 | 人氣 0 | 評價 10 | 評價/貼文 0.26 | 送出評價 7 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2012/1/3 下午 12:42:51
void infix_to_prefix()
{
int rear=0, top=0, flag=0,i=0;
char stack_t[MAX];
for (i=0; i<MAX; i++)
stack_t[i]='\0';
gets(infix_q);//使用者輸入的值 (2+(3*4))
i=0;
while(infix_q[i]!='\0') //infix[0]=( infix[1]=2 infix[2]=+ infix[3]=( infix[4]=3 infix[5]=* infix[4] infix[5]=) infix[6]=) rear=7
{
     i++;
     rear++;
     }
infix_q[rear] = 'q'; //於佇列加入q為結束符號 //infix[7]='q'
cout<<"\t"<<"後序表示法 : ";
stack_t[top] = 'q'; //於堆疊加入q為結束符號 //stack_t[0]='q'
for (flag = 0; flag <= rear; flag++)\
     {
switch (infix_q[flag])
     {
//輸入為),則輸出堆疊內運算子,直到堆疊內為(
case ')':
while(stack_t[top]!='(')
cout<<setw(1)<<stack_t[top--];
top--;
break;
//輸入為q,則將堆疊內還未輸出的運算子輸出
case 'q':
while(stack_t[top]!='q')
cout<<setw(1)<<stack_t[top--];
break;
//輸入為運算子,若小於TOP在堆疊中所指運算子,
     //則將堆疊所指運算子輸出,若大於等於TOP在堆疊
     //中所指運算子,則將輸入之運算子放入堆疊
case '(':
case '^':
case '*':
case '/':
case '+':
case '-':
while (compare(stack_t[top], infix_q[flag])==1)
cout<<setw(1)<<stack_t[top--];
stack_t[++top] = infix_q[flag];
break;
//輸入為運算元,則直接輸出
default :
cout<<setw(1)<<infix_q[flag];
break;
}
}
}

以上是中轉後
是這樣的,中轉後我能理解
但中轉前,我卻不知該怎麼改它

是有些頭緒,但很亂...所以文章中先不改
作者 : x2163126(吃冬瓜補西瓜)
[ 貼文 38 | 人氣 0 | 評價 10 | 評價/貼文 0.26 | 送出評價 7 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2012/1/3 下午 12:47:35
#include <iostream>
#include <cstdlib>
#include <iomanip>
using namespace std;
#define MAX 50
char infix_q[MAX]; //用來存放中序表示法的佇列
//運算子優先權的比較,若輸入運算子小於堆疊中運算子
//,則傳回值為1,否則為0
int compare(char stack_o, char infix_o)
{
//在中序表示法佇列及暫存堆疊中,運算子的優先順序表,
//其優先權值為INDEX/2
    char infix_priority[9] ;
char stack_priority[8] ;
int index_s=0, index_i=0;
infix_priority[0]='q';infix_priority[1]=')';
infix_priority[2]='+';infix_priority[3]='-';
infix_priority[4]='*';infix_priority[5]='/';
infix_priority[6]='^';infix_priority[7]=' ';
infix_priority[8]='(';
stack_priority[0]='q';stack_priority[1]='(';
stack_priority[2]='+';stack_priority[3]='-';
stack_priority[4]='*';stack_priority[5]='/';
stack_priority[6]='^';stack_priority[7]=' ';
while (stack_priority[index_s] != stack_o)
index_s++;
while (infix_priority[index_i] != infix_o)
index_i++;
return ((int)(index_s/2) >= (int)(index_i/2) ? 1 : 0);
}

//程式第一段
作者 : x2163126(吃冬瓜補西瓜)
[ 貼文 38 | 人氣 0 | 評價 10 | 評價/貼文 0.26 | 送出評價 7 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2012/1/3 下午 12:48:05
//中序轉後序的方法
void infix_to_postfix()
{
int rear=0, top=0, flag=0,i=0;
char stack_t[MAX];
for (i=0; i<MAX; i++)
stack_t[i]='\0';
gets(infix_q);
i=0;
while(infix_q[i]!='\0')
{
     i++;
     rear++;
     }
infix_q[rear] = 'q'; //於佇列加入q為結束符號
cout<<"\t"<<"後序表示法 : ";
stack_t[top] = 'q'; //於堆疊加入q為結束符號
for (flag = 0; flag <= rear; flag++)\
     {
switch (infix_q[flag])
     {
//輸入為),則輸出堆疊內運算子,直到堆疊內為(
case ')':
while(stack_t[top]!='(')
cout<<setw(1)<<stack_t[top--];
top--;
break;
//輸入為q,則將堆疊內還未輸出的運算子輸出
case 'q':
while(stack_t[top]!='q')
cout<<setw(1)<<stack_t[top--];
break;
//輸入為運算子,若小於TOP在堆疊中所指運算子,
     //則將堆疊所指運算子輸出,若大於等於TOP在堆疊
     //中所指運算子,則將輸入之運算子放入堆疊
case '(':
case '^':
case '*':
case '/':
case '+':
case '-':
while (compare(stack_t[top], infix_q[flag])==1)
cout<<setw(1)<<stack_t[top--];
stack_t[++top] = infix_q[flag];
break;
//輸入為運算元,則直接輸出
default :
cout<<setw(1)<<infix_q[flag];
break;
}
}
}


//主函數宣告
int main (void)
{
    int i=0;
    for (i=0; i<MAX; i++)
infix_q[i]='\0';
cout<<"\t=========================================="<<endl;
//cout<<"\t本程式會將其轉成後序運算式"<<endl;
    cout<<"\t請輸入中序運算式"<<endl;
    cout<<"\t例如:(9+3)*8+7*6-8/4 "<<endl;
    cout<<"\t可以使用的運算子包括:^,*,+,-,/,(,)等 "<<endl;
    cout<<"\t=========================================="<<endl;
    cout<<"\t請開始輸入中序運算式: ";
    infix_to_postfix();
    cout<<endl;
    cout<<"\t=========================================="<<endl;
    system("pause");
    return 0;
}
//程式第二段
作者 : x2163126(吃冬瓜補西瓜)
[ 貼文 38 | 人氣 0 | 評價 10 | 評價/貼文 0.26 | 送出評價 7 次 ] 
[ 給個讚 ]  [ 給個讚 ]  [ 回應本文 ]  [ 發表新文 ]  [ 回上頁 ] [ 回討論區列表 ] [ 回知識入口 ]
2012/1/3 下午 02:12:03
如果要將中序式轉為前序式,則在讀取中序式時是由後往前讀取,而左右括號的處理方式相反,其餘不變,但輸出之前必須先置入堆疊,待轉換完成後再將堆疊中的 值由上往下讀出,如此就是前序表示式。

根據規則來修改

讀取中序式時是由後往前讀取
由右讀到左
這樣我是要把程式的for改為
for (flag = rear; flag <= 0; flag--)

左右括號的處理方式相反
case '(':
while(stack_t[top]!=')')
cout<<setw(1)<<stack_t[top--];
top--;
break;
case '(':
...
然後呢!!
 板主 : simula
 > C++ - 討論區
 - 最近熱門問答精華集
 - 全部歷史問答精華集
 - C++ - 知識庫
  ■ 全站最新Post列表
  ■ 我的文章收藏
  ■ 我最愛的作者
  ■ 全站文章收藏排行榜
  ■ 全站最愛作者排行榜
  ■  月熱門主題
  ■  季熱門主題
  ■  熱門主題Top 20
  ■  本區Post排行榜
  ■  本區評價排行榜
  ■  全站專家名人榜
  ■  全站Post排行榜
  ■  全站評價排行榜
  ■  全站人氣排行榜
 請輸入關鍵字 
  開始搜尋
 
Top 10
評價排行
C++
1 Raymond 12510 
2 simula 4690 
3 青衫 4640 
4 coco 3850 
5 白老鼠(Gary) 3610 
6 Ben 2250 
7 Anderson 1960 
8 ozzy 1790 
9 windblown 1650 
10 Kenny 1540 
C++
  專家等級 評價  
  一代宗師 10000  
  曠世奇才 5000  
  頂尖高手 3000  
  卓越專家 1500  
  優秀好手 750  
Microsoft Internet Explorer 6.0. Screen 1024x768 pixel. High Color (16 bit).
2000-2014 程式設計俱樂部 http://www.programmer-club.com.tw/
0.171875