【本文原創於Silence•軒轅•寂的博客園技術博客。】
【本文歡迎轉載，轉載請以鏈接形式注明出處。】
【本博客所有文章都經博主精心整理，請尊重我的勞動成果。】
①數制轉換：
將一個非負的十進制整數N轉換為另一個等價的基為B的B進制數的問題，很容易通過"除B取余法"來解決。
【例】將十進制數13轉化為二進制數。
解答：按除2取余法，得到的余數依次是1、0、1、1，則十進制數轉化為二進制數為1101。
分析：由於 最先得到 的余數是轉化結果的 最低位 ，最後得到的余數是轉化結果的最高位，因此很容易用棧來解決。
具體算法如下：
1 #include <STACK> //C++中使用棧要包含的頭文件
2 using namespace std;//這個也是要加的
3
4 void conversion(int N,int B)
5 {//假設N是非負的十進制整數，輸出等值的B進制數
6
7 stack<int> S; //創建一個元素類型為int型的空棧
8 while(N)
9 {
10 S.push(N%B); //將轉換後的數值，從底位到高位開始入棧
11 N=N/B;
12 }
13 while(!S.empty())//棧非空時退棧輸出
14 {
15 printf("%d",S.top()); //打印棧頂元素
16 S.pop(); //將棧頂元素出棧
17 }
18 }
19
20 int main()
21 {
22 conversion(10,2);
23 }
表達式求值是程序設計語言編譯中的一個最基本的問題。我們討論一種簡單直觀的方法“算法優先級法”
算術四則運算的規則 ：
1、從左到右
2、先乘除後加減
3、先括號內，後括號外
相繼出現的兩個運算符優先級如下圖：
【例】4 + 2*3 -10/5 每一步的計算順序應該是：
4 + 2*3 -10/5 = 4 + 6 - 10/5 = 10 - 10/5 = 10 - 2 = 8
算法步驟 ：（我們假設表達式以字符‘#’結尾）
（1）首先，創建空運算符棧OPTR，將表達式起始符‘#’壓入棧底，創建空操作數棧OPND
（2）依次讀入表達式中的每個字符，若是操作數則進操作數棧，若是運算符則和運算符棧頂的運算符比較優先級後，做如下相應操作：
1.如果棧頂的運算符優先級較低，則把新的運算符壓入OPTR；執行（2）
2.如果棧頂的運算符優先級較高，則將其 和 操作數棧的兩個棧頂元素 退棧，計算3個元素組成的表達式的值，再壓入操作數棧，然後繼續判斷；
3.如果棧頂的運算符優先級相等（除了#符外，只有‘(’和‘)’是相等的），則將‘（’出棧；執行（2）
（3）直到整個表達式求值完畢（即OPTR棧頂元素和當前讀入的字符均為‘#’）
具體算法實現： 1 #include <iostream>
2 #include <stack>//C++中使用棧要包含的頭文件
3
4 using namespace std;
5
6 //符號數組
7 char symbol[7] = {'+', '-', '*', '/', '(', ')', '#'};
8
9 //棧內元素的優先級
10 int in[7] = {3, 3, 5, 5, 1, 6, 0};
11
12 //棧外元素的優先級
13 int out[7] = {2, 2, 4, 4, 6, 1, 0};
14
15 /*
16 * 通過符號字符獲取它的數組下標
17 */
18 int get(char c)
19 {
20 switch(c)
21 {
22 case '+':
23 return 0;
24 case '-':
25 return 1;
26 case '*':
27 return 2;
28 case '/':
29 return 3;
30 case '(':
31 return 4;
32 case ')':
33 return 5;
34 case '#':
35 return 6;
36 default:
37 return 6;
38 }
39 }
40
41 /*
42 * 比較棧內運算符c1和棧外運算符c2的優先級
43 */
44 char precede(char c1, char c2)
45 {
46 int i1 = get(c1);
47 int i2 = get(c2);
48
49 if(in[i1] > out[i2])
50 {
51 return '>';
52 }
53 else if(in[i1] < out[i2])
54 {
55 return '<';
56 }
57 else
58 {
59 return '=';
60 }
61 }
62
63 /*
64 * 計算基本表達式的值
65 */
66 int figure(int a, int theta, int b)
67 {
68 switch(theta)
69 {
70 case 0:
71 return a + b;
72 case 1:
73 return a - b;
74 case 2:
75 return a * b;
76 default:
77 return a / b;
78 }
79 }
80
81 /*
82 * 計算表達式的值
83 */
84 int EvaluateExpression(const char *exp)
85 {
86 stack<int> OPND; //操作數棧
87 stack<int> OPTR; //運算符棧
88 OPTR.push(get('#'));
89
90 int flag = 1; //表示正負號 1,表示正 0,表示負
91 int a, theta, b;
92
93 if(!('+' == *exp || '-' == *exp || '(' == *exp || isdigit(*exp)))
94 {//如果不是以'+'、'-'、'('或者數字的其中一個開頭，則表達式錯誤
95 cout << "表達式出錯1" << endl;
96 return -1;
97 }
98 if('+' == *exp)
99 {
100 exp++;//指向下一個字符
101 }
102 else if('-' == *exp)
103 {
104 flag = 0;
105 exp++;//指向下一個字符
106 }
107
108 int index = OPTR.top(); //獲取運算符棧頂元素在數組的下標號
109 while(*exp || symbol[index] != '#') //如果棧頂元素是'#'且當前元素為空結束計算
110 {
111 if(isdigit(*exp))
112 {//如果當前元素是數字，計算整個操作數的值，然後壓入操作數棧
113 int sum = 0;
114 while(isdigit(*exp))
115 {//計算操作數的值
116 sum = sum * 10 + (*exp - '0');
117 exp++;
118 }
119 if (!flag) //如果是負數
120 {
121 sum = -sum;
122 }
123 OPND.push(sum);
124 flag = 1;
125 }
126 else
127 {//如果不是數字
128 switch(precede(symbol[OPTR.top()], *exp))//比較棧頂運算符和當前運算符的優先級
129 {
130 case '>' :
131 b = OPND.top();
132 OPND.pop();
133 a = OPND.top();
134 OPND.pop();
135 theta = OPTR.top();
136 OPTR.pop();
137 OPND.push(figure(a, theta, b));
138 break;
139 case '<' :
140 OPTR.push(get(*exp));
141 if(*exp)
142 {
143 exp++;
144 }
145 break;
146 case '=' :
147 OPTR.pop();
148 if(*exp)
149 {
150 exp++;
151 }
152 break;
153 }
154 }
155 index = OPTR.top();
156 }
157 return OPND.top();
158 }
159
160 int main()
161 {
162 char c[50] = {0};
163 cout << "請輸入一個表達式: ";
164 cin.getline(c,50);
165 cout << EvaluateExpression(c) << endl;
166
167 return 0;
168 }
1 #include <QUEUE><span >//C++中使用隊列要包含的頭文件</span>
2
3
4 using namespace std;
5 typedef struct
6 {
7 char name[20];
8 char sex; //性別，'F'表示女性，'M'表示男性
9 }Person;
10
11 void DancePartner(Person dancer[],int num)
12 {//結構數組dancer中存放跳舞的男女，num是跳舞的人數。
13
14 Person p;
15 queue<Person> Mdancers,Fdancers;
16
17 for(int i = 0; i < num; i++)
18 {//依次將跳舞者依其性別入隊
19 p=dancer[i];
20 if(p.sex=='F')
21 Fdancers.push(p); //排入女隊
22 else
23 Mdancers.push(p); //排入男隊
24 }
25 printf("The dancing partners are: \n \n");
26 while(!(Fdancers.empty()||Mdancers.empty()))
27 {
28 //依次輸入男女舞伴名
29 p=Fdancers.front(); //獲取女隊第一人
30 Fdancers.pop(); //出隊
31 printf("%s ",p.name); //打印出隊女士名
32
33 p=Mdancers.front(); //獲取男隊第一人
34 Mdancers.pop(); //出隊
35 printf("%s\n",p.name); //打印出隊男士名
36 }
37 if(!Fdancers.empty())
38 {//輸出女士剩余人數及隊頭女士的名字
39 printf("\n There are %d women waitin for the next round.\n",Fdancers.size());
40 p=Fdancers.front(); //取隊頭
41 printf("%s will be the first to get a partner. \n",p.name);
42 }
43 else if(!Mdancers.empty())
44 {//輸出男隊剩余人數及隊頭者名字
45 printf("\n There are%d men waiting for the next round.\n",Mdancers.size());
46 p=Mdancers.front();
47 printf("%s will be the first to get a partner.\n",p.name);
48 }
49 else
50 {
51 printf("There is not person in the queue!");
52 }
53 }//DancerPartners
54
55 int main()
56 {
57 Person p[] = {{"A",'F'},{"B",'F'},{"C",'M'},{"D",'M'}};
58 DancePartner(p,4);
59 }
