2011 08 27 四則運算 ( 可含括號 )

buy

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



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

& 如何實作五則運算

buy

http://zerojudge.tw/ShowProblem?problemid=a017   解答

1. #include<iostream>
   
2. #include<sstream>
   
3. using namespace std;
   
4. 
   
5. int order(char op);
   
6. string infixToPofix(string infix);
   
7. int pofixComput(string pofix);
   
8. 
   
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. }
    
19. 
    
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. }
    
35. 
    
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.     }
    
90. 
    
91.     return pofix.str();   
    
92. }
    
93. 
    
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. }

複製代碼