Board logo

標題: 2011 1001 (中序轉後序 ) [打印本頁]
作者: buy    時間: 2011-10-1 20:31     標題: 2011 1001 (中序轉後序 )

  1. // Test.cpp : 定義主控台應用程式的進入點。
  2. //

  4. #include "stdafx.h"      // 不要管
  5. #include<iostream>
  6. #include<sstream>
  7. using namespace std;

  9. //宣告一個資料型態叫做Stack
  10. class StackChar{
  11.         private:
  12.                 int top;  //紀錄目前index位置
  13.         public:
  14.                 char stack[1000];  //放資料的地方

  16.                 StackChar()
  17.                 {
  18.                         top = -1;   // 沒有東西
  19.                 };

  21.                 void push(char input)
  22.                 {
  23.                         stack[++top] = input;
  24.                 };

  26.                 char pop()
  27.                 {
  28.                         return stack[top--];
  29.                 };

  31.                 char peak()
  32.                 {
  33.                         return stack[top];
  34.                 };

  36.                 bool IsEmpty()
  37.                 {
  38.                         return (top <= -1)? true : false;
  39.                 }
  40. };

  42. //宣告一個資料型態叫做Stack
  43. class StackInteger{
  44.         private:
  45.                 int top;  //紀錄目前index位置
  46.         public:
  47.                 int stack[1000];  //放資料的地方

  49.                 StackInteger()
  50.                 {
  51.                         top = -1;   // 沒有東西
  52.                 };

  54.                 void push(int input)
  55.                 {
  56.                         stack[++top] = input;
  57.                 };

  59.                 int pop()
  60.                 {
  61.                         return stack[top--];
  62.                 };

  64.                 int peak()
  65.                 {
  66.                         return stack[top];
  67.                 };

  69.                 bool IsEmpty()
  70.                 {
  71.                         return (top <= -1)? true : false;
  72.                 }
  73. };


  76. int order(char op);   // 取得 算數優先權 */ > +-
  77. string infixToPostfix(string infix);   // 中序轉後序
  78. int pofixComput(string pofix);

  80. int _tmain(int argc, _TCHAR* argv[])    //int main()
  81. {
  82.         string input;
  83.         getline(cin, input);
  84.         //string postfix = infixToPostfix(input);

  86.         cout << endl << pofixComput(
  87.                  infixToPostfix(input)
  88.                 );


  91.         string str;
  92.         getline(cin, str);
  93.         return 0;
  94. }

  96. // 取得 算數優先權 */ > +-
  97. int order(char op)
  98. {
  99.         int returnValue = 0;
  100.         switch(op)
  101.         {
  102.                 case '*' :
  103.                 case '/' :
  104.                         returnValue = 2;
  105.                         break;
  106.                 case  '+':
  107.                 case  '-':
  108.                         returnValue = 1;
  109.                         break;
  110.                 default:
  111.                         returnValue = 0;
  112.                         break;
  113.         }
  114.         return returnValue;
  115. }

  117. // 中序轉後序
  118. string infixToPostfix(string infix)
  119. {
  120.         istringstream issstream(infix);  //輸入
  121.         ostringstream postfix;  //輸出
  122.         string word;  // 暫時儲存 temp

  124.         StackChar stack;
  125.         while(issstream >> word)
  126.         {
  127.                 if( isdigit(word[0]))
  128.                 {
  129.                         postfix << word << " ";
  130.                 }
  131.                 else
  132.                 {
  133.                         switch(word[0])
  134.                         {
  135.                                 case '(':
  136.                                         stack.push('(');
  137.                                         break;

  139.                                 case ')':
  140.                                         while(stack.peak() != '('  )
  141.                                         {
  142.                                                 postfix << stack.pop() << " ";
  143.                                         }
  144.                                         stack.pop();
  145.                                         break;

  147.                                 case '+':   case '-': case '*':   case '/':
  148.                                         if( stack.IsEmpty())   //如果Stack沒資料
  149.                                         {
  150.                                                 stack.push(word[0]);
  151.                                         }
  152.                                         else  //如果Stack至少有一個資料
  153.                                         {
  154.                                                 if( order(word[0]  ) > order( stack.peak() ) )
  155.                                                 {
  156.                                                         stack.push(word[0]);
  157.                                                 }
  158.                                                 else
  159.                                                 {
  160.                                                         do{
  161.                                                                 postfix << stack.pop() << " ";
  162.                                                         }while //如果還有資料 且 優先權小於等於目前的word[0]，繼續pop()
  163.                                                                 ( !stack.IsEmpty() &&  
  164.                                                                    order(word[0]) <= order( stack.peak() )
  165.                                                                 );
  166.                                                         stack.push(word[0]);
  167.                                                 }
  168.                                         }
  169.                                         break;

  171.                                 default:
  172.                                         break;
  173.                         }
  174.                 }
  175.         }

  177.         //清空stack
  178.         if(stack.IsEmpty()  ) //如果沒資料
  179.         {
  180.                 ;
  181.         }
  182.         else
  183.         {
  184.                 do{
  185.                         postfix << stack.pop() << " ";
  186.                 }while(  !stack.IsEmpty() );
  187.         }
  188.         return postfix.str();
  189. }

  191. // 後序 計算
  192. int pofixComput(string pofix)
  193. {
  194.         istringstream issstream(pofix);  //輸入
  195.         string word;
  196.         StackInteger stackInt;

  198.                         int i , j ;
  199.         while( issstream >>word  )
  200.         {
  201.                 if(isdigit(word[0])) //如果是數字
  202.         {
  203.                         stackInt.push(  
  204.                                          atoi(word.c_str())
  205.                                 );
  206.                 }
  207.                 else   // 如果不是數字
  208.                 {
  209.                         i = stackInt.pop();
  210.                         j = stackInt.pop();
  211.                         switch(word[0])
  212.                         {
  213.                                  case '+':   
  214.                                          stackInt.push(j + i);
  215.                                          break;
  216.                                  case '-':
  217.                                          stackInt.push(j - i);
  218.                                          break;
  219.                                  case '*':   
  220.                                          stackInt.push(j * i);
  221.                                          break;
  222.                                  case '/':
  223.                                          stackInt.push(j / i);
  224.                                          break;
  225.                                  default:
  226.                                          break;
  227.                         }
  228.                 }
  229.         }  // End While

  231.         return stackInt.pop();
  232. }
複製代碼




歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/) Powered by Discuz! 7.2