Board logo

標題: 2011 08 27 四則運算 ( 可含括號 ) [打印本頁]
作者: buy    時間: 2011-8-27 10:48     標題: 2011 08 27 四則運算 ( 可含括號 )

目前四則運算可以使用括號

[attach]415[/attach]

請考慮 5+((123)+456)*23-345 為何會出錯

& 如何實作五則運算
作者: buy    時間: 2011-8-27 10:50

http://zerojudge.tw/ShowProblem?problemid=a017   解答
  1. #include<iostream>
  2. #include<sstream>
  3. using namespace std;

  5. int order(char op);
  6. string infixToPofix(string infix);
  7. int pofixComput(string pofix);

  9. int main()
  10. {
  11.     string input;
  12.   
  13.     while(getline(cin, input))
  14.     {
  15.         string pofix = infixToPofix(input);//中序式轉後序式
  16.         cout << pofixComput(pofix) << endl;//後序式運算
  17.     }
  18. }

  20. int order(char op)
  21. {
  22.     switch(op)
  23.     {
  24.         case'(' :
  25.             return -1;
  26.             break;
  27.         case '+' :
  28.         case '-' :
  29.             return 0;
  30.             break;
  31.         default :// * / %
  32.             return 1;
  33.     }
  34. }

  36. string infixToPofix(string infix)
  37. {
  38.     istringstream isstream(infix);
  39.     ostringstream pofix;
  40.     string word;
  41.     char opStack[1000];
  42.     int top_Op = 0;
  43.     while(isstream >> word)
  44.     {                     
  45.         if(isdigit(word[0]))
  46.         {
  47.             pofix << word << " ";//數字直接輸出
  48.         }
  49.         else//運算子
  50.         {
  51.             switch(word[0])
  52.             {
  53.                 case '(' : //左括弧直接進入堆疊
  54.                     opStack[top_Op++] = word[0];
  55.                     break;
  56.                     
  57.                 case ')' : //右括弧 ，輸出至左括弧停止
  58.                     while(opStack[top_Op-1]!='(')//一個左括弧搭配一個又括弧，top_Op-1必大於-1
  59.                     {
  60.                         pofix << opStack[--top_Op] << " ";
  61.                     }
  62.                     top_Op--;//左括弧不輸出  略過
  63.                     break;
  64.                     
  65.                 case '+' : case'-' : case '*' : case '/' : case '%'://加減乘除餘
  66.                     if(top_Op-1>=0)//避免超出陣列範圍
  67.                         while(order(opStack[top_Op-1]) >= order(word[0])&&top_Op-1>=0)
  68.                         {//持續輸出  堆疊中比自己優先的運算子
  69.                             pofix << opStack[--top_Op] << " ";
  70.                                 //cout << "輸出" << opStack[top_Op] << "top:" << top_Op;
  71.                         }
  72.                         //放入堆疊
  73.                         //cout << "放入堆疊";
  74.                     opStack[top_Op++] = word[0];
  75.                     break;
  76.                     
  77.                     default :
  78.                         break;
  79.             }
  80.         }
  81.                     
  82.     }
  83.         //讀完全部  全部輸出直到堆疊為空
  84.        // cout << "輸出至空" ;
  85.     while(top_Op-1>=0)
  86.     {
  87.         pofix << opStack[--top_Op] << " ";
  88.         //cout << "輸出" << opStack[top_Op];            
  89.     }

  91.     return pofix.str();   
  92. }

  94. int pofixComput(string pofix)
  95. {
  96.     int stack[1000];
  97.     int top = 0;
  98.     istringstream read(pofix);
  99.     string word;
  100.     while(read >> word)
  101.     {
  102.         if(isdigit(word[0]))
  103.         {
  104.             stack[top++] = atoi(word.c_str());
  105.         }
  106.         else
  107.         {
  108.             switch(word[0])
  109.             {
  110.                 case '+' :
  111.                     stack[top-2] = stack[top-2] + stack[top-1];
  112.                     top -= 1;
  113.                     break;
  114.                 case '-' :
  115.                     stack[top-2] = stack[top-2] - stack[top-1];
  116.                     top -= 1;
  117.                     break;
  118.                 case '*' :
  119.                     stack[top-2] = stack[top-2] * stack[top-1];
  120.                     top -= 1;
  121.                     break;
  122.                 case '/' :
  123.                     stack[top-2] = stack[top-2] / stack[top-1];
  124.                     top -= 1;
  125.                     break;
  126.                 case '%' :
  127.                     stack[top-2] = stack[top-2] % stack[top-1];
  128.                     top -= 1;
  129.                     break;
  130.             }
  131.         }
  132.     }
  133.     return stack[0];
  134. }
複製代碼




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