计算机考研机试指南（六） ——栈
机试指南 cha 3 栈的应用
括号匹配问题
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <queue> 5 #include <stack> 6 #include <math.h> 7 #include <string> 8 #include <string.h> 9 #include <stdlib.h> 10 #include <stack> 11 using namespace std; 12 13 /* 14 问题：cha 3 栈的应用 括号匹配问题 15 思路：如果直接在压栈的时候输出，则连续出现多个((((的$不能及时输出， 16 必须要等到输入串遍历结束后，站内剩余(((才能将其对应输出串位置修改为$ 17 18 2 压栈的内容是字符还是字符在字符串中的索引位置？如果是字符则无法找到并修改ans中的字符 19 */ 20 21 char ans[101]; 22 void match(char c[101]) 23 { 24 stack<int> s; 25 int i = 0; 26 while (c[i] !=\'\0\') 27 { 28 // 如果为）且为栈底则输出？，如果为（且为栈底则输出$,如果为其他字符则不压栈输出空格 29 // 如果为左括号则压栈，右括号则判断栈顶，如果为（则弹栈 30 if (c[i] == \')\'&& s.empty()) 31 ans[i] = \'?\'; 32 else if (c[i] == \'(\') 33 { 34 s.push(i); 35 ans[i] = \' \'; 36 } 37 else if (c[i] == \')\' && c[s.top()] == \'(\') 38 { 39 s.pop(); 40 ans[i] = \' \'; 41 } 42 else 43 ans[i] =\' \'; 44 i++; 45 } 46 while (!s.empty()) 47 { 48 ans[s.top()] = \'$\'; 49 s.pop(); 50 } 51 ans[i] = \'\0\'; 52 } 53 int main() 54 { 55 char c[101]; 56 cin >> c; 57 cout << c << endl; 58 match(c); // 输出匹配的符号 59 cout << ans << endl; 60 61 return 0; 62 }
表达式求值（课本）
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <queue> 5 #include <stack> 6 #include <math.h> 7 #include <string> 8 #include <string.h> 9 #include <stdlib.h> 10 #include <stack> 11 using namespace std; 12 13 /* 14 问题 ： 简单计算器（表达式求值） 15 16 */ 17 18 bool isNum(char c) 19 { 20 int num = c-\'0\'; 21 if (num >= 0 && num <= 9) 22 return true; 23 else 24 return false; 25 } 26 27 char op[8][8] = 28 { 29 \'0\',\'+\',\'-\',\'*\',\'/\',\'(\',\')\',\'#\', 30 \'+\',\'>\',\'>\',\'<\',\'<\',\'<\',\'>\',\'>\', 31 \'-\',\'>\',\'>\',\'<\',\'<\',\'<\',\'>\',\'>\', 32 \'*\',\'>\',\'>\',\'>\',\'>\',\'<\',\'>\',\'>\', 33 \'/\',\'>\',\'>\',\'>\',\'>\',\'<\',\'>\',\'>\', 34 \'(\',\'<\',\'<\',\'<\',\'<\',\'<\',\'=\',\'>\', 35 \')\',\'>\',\'>\',\'>\',\'>\',\'0\',\'>\',\'>\', 36 \'#\',\'<\',\'<\',\'<\',\'<\',\'<\',\'0\',\'=\', 37 }; 38 char compare(char a,char b) 39 { 40 int x,y; 41 for (int i = 1;i < 8;i++) 42 if (op[i][0] == a) 43 x = i; 44 for (int i = 1;i < 8;i++) 45 if (op[0][i] == b) 46 y = i; 47 return op[x][y]; 48 } 49 int cal(int a,char op,int b) 50 { 51 switch (op) 52 { 53 case \'+\':return a+b;break; 54 case \'-\':return b-a;break; 55 case \'*\':return a*b;break; 56 case \'/\':return b/a; 57 } 58 } 59 int main() 60 { 61 char c[201]; 62 stack<char> oper; 63 stack<int> number; 64 oper.push(\'#\'); 65 while (cin>>c) 66 { 67 if (c[0] ==\'0\') 68 break; 69 int i = 0; 70 while (c[i] != \'#\' || oper.top()!= \'#\') 71 { 72 if (isNum(c[i])) 73 { 74 number.push(c[i]-\'0\'); 75 i = i+1; 76 continue; 77 } 78 switch(compare(oper.top(),c[i])) 79 { 80 case \'<\': 81 // 继续压栈 82 oper.push(c[i]); 83 i = i+1; 84 break; 85 case \'=\': 86 // 弹栈 87 oper.pop(); 88 i = i+1; 89 break; 90 case \'>\': 91 // 栈顶为优先级高的运算符，进行计算后压栈 92 char oper1 = oper.top(); 93 oper.pop(); 94 int num1 = number.top(); 95 number.pop(); 96 int num2 = number.top(); 97 number.pop(); 98 int ans = cal(num1,oper1,num2); 99 number.push(ans); 100 // 此时c[i]符号并没有压入栈中，所以不用i+2 101 102 } 103 } 104 cout << number.top()<<endl; 105 } 106 107 return 0; 108 }
局限性：输入的表达式中数字不能是大于9的整数
改进的表达式求值（计算大于9的整数）
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <queue> 5 #include <stack> 6 #include <math.h> 7 #include <string> 8 #include <string.h> 9 #include <stdlib.h> 10 #include <stack> 11 using namespace std; 12 13 /* 14 问题 ： 简单计算器（表达式求值） 15 16 */ 17 18 bool isNum(char c[]) 19 { 20 int num = c[0]-\'0\'; 21 if (num >= 0 && num <= 9) 22 return true; 23 else 24 return false; 25 } 26 int Num(char c[]) 27 { 28 // 计算数字的值 29 int sum=0; 30 int i=0; 31 while (c[i]!=\'\0\') 32 { 33 int a = c[i]-\'0\'; 34 // cout << c[i]; 35 sum = sum*10+a; 36 i++; 37 } 38 return sum; 39 } 40 char op[8][8] = 41 { 42 \'0\',\'+\',\'-\',\'*\',\'/\',\'(\',\')\',\'#\', 43 \'+\',\'>\',\'>\',\'<\',\'<\',\'<\',\'>\',\'>\', 44 \'-\',\'>\',\'>\',\'<\',\'<\',\'<\',\'>\',\'>\', 45 \'*\',\'>\',\'>\',\'>\',\'>\',\'<\',\'>\',\'>\', 46 \'/\',\'>\',\'>\',\'>\',\'>\',\'<\',\'>\',\'>\', 47 \'(\',\'<\',\'<\',\'<\',\'<\',\'<\',\'=\',\'>\', 48 \')\',\'>\',\'>\',\'>\',\'>\',\'0\',\'>\',\'>\', 49 \'#\',\'<\',\'<\',\'<\',\'<\',\'<\',\'0\',\'=\', 50 }; 51 char compare(char a,char b) 52 { 53 int x,y; 54 for (int i = 1;i < 8;i++) 55 if (op[i][0] == a) 56 x = i; 57 for (int i = 1;i < 8;i++) 58 if (op[0][i] == b) 59 y = i; 60 return op[x][y]; 61 } 62 int cal(int a,char op,int b) 63 { 64 switch (op) 65 { 66 case \'+\':return a+b;break; 67 case \'-\':return b-a;break; 68 case \'*\':return a*b;break; 69 case \'/\':return b/a; 70 } 71 } 72 int main() 73 { 74 char c[10]; 75 stack<char> oper; 76 stack<int> number; 77 oper.push(\'#\'); 78 79 while (cin>>c){// 每次仅输入一个单词，如果是运算符则c[0],数字则需要计算一下 80 int i = 0; 81 if (c[0] == \'0\') 82 break; 83 while (c[i] != \'#\' || oper.top()!= \'#\') 84 { 85 if (isNum(c)) 86 { 87 number.push(Num(c)); 88 // cout << Num(c) << endl; 89 cin >> c; 90 continue; 91 } 92 switch(compare(oper.top(),c[i])) 93 { 94 case \'<\': 95 // 继续压栈 96 oper.push(c[i]); 97 cin >> c; 98 break; 99 case \'=\': 100 // 弹栈 101 oper.pop(); 102 cin >> c; 103 break; 104 case \'>\': 105 // 栈顶为优先级高的运算符，进行计算后压栈 106 char oper1 = oper.top(); 107 oper.pop(); 108 int num1 = number.top(); 109 number.pop(); 110 int num2 = number.top(); 111 number.pop(); 112 int ans = cal(num1,oper1,num2); 113 number.push(ans); 114 // 此时c[i]符号并没有压入栈中，所以不用i+2 115 116 } 117 } 118 cout << number.top()<<endl; 119 } 120 121 return 0; 122 }
测试用例：
10 + 2 * 3 – 8 / ( 3 + 1 ) #
0
简单计算器 2006年浙江大学计算机及软件工程研究生机试真题
这个题第一天重新写了一下课本上的实现方法，第二天改进成可以计算大于9的的算术表达式，第三天修改成符合这道机试题格式要求的题目。
自己还差的很远。
1 #include <iostream> 2 #include <stdio.h> 3 #include <algorithm> 4 #include <queue> 5 #include <stack> 6 #include <math.h> 7 #include <string> 8 #include <string.h> 9 #include <stdlib.h> 10 #include <stack> 11 using namespace std; 12 13 /* 14 问题 ： 简单计算器（表达式求值） 15 改进版3：输入串末尾没有#如何控制，用字符后面有没有空格来控制 16 17 */ 18 19 bool isNum(char c[],int i) 20 { 21 int num = c[i]-\'0\'; 22 if (num >= 0 && num <= 9) 23 return true; 24 else 25 return false; 26 } 27 int Num(char c[],int &i) 28 { 29 // 计算数字的值 30 int sum=0; 31 while (c[i]!=\' \' && c[i]!=\'\0\') 32 { 33 int a = c[i]-\'0\'; 34 // cout << c[i]; 35 sum = sum*10+a; 36 i++; 37 } 38 return sum; 39 } 40 char op[8][8] = 41 { 42 \'0\',\'+\',\'-\',\'*\',\'/\',\'(\',\')\',\'\0\', 43 \'+\',\'>\',\'>\',\'<\',\'<\',\'<\',\'>\',\'>\', 44 \'-\',\'>\',\'>\',\'<\',\'<\',\'<\',\'>\',\'>\', 45 \'*\',\'>\',\'>\',\'>\',\'>\',\'<\',\'>\',\'>\', 46 \'/\',\'>\',\'>\',\'>\',\'>\',\'<\',\'>\',\'>\', 47 \'(\',\'<\',\'<\',\'<\',\'<\',\'<\',\'=\',\'>\', 48 \')\',\'>\',\'>\',\'>\',\'>\',\'0\',\'>\',\'>\', 49 \'\0\',\'<\',\'<\',\'<\',\'<\',\'<\',\'0\',\'=\', 50 }; 51 char compare(char a,char b) 52 { 53 int x,y; 54 for (int i = 1;i < 8;i++) 55 if (op[i][0] == a) 56 x = i; 57 for (int i = 1;i < 8;i++) 58 if (op[0][i] == b) 59 y = i; 60 return op[x][y]; 61 } 62 float cal(float a,char op,float b) 63 { 64 switch (op) 65 { 66 case \'+\':return a+b;break; 67 case \'-\':return b-a;break; 68 case \'*\':return a*b;break; 69 case \'/\':return b/a; 70 } 71 return 0; 72 } 73 int main() 74 { 75 char c[50]; 76 stack<char> oper; 77 stack<float> number; 78 oper.push(\'\0\'); 79 80 while (cin.getline(c,1000)){// 输入一行字符 81 int i = 0; 82 if (c[0] == \'0\') 83 break; 84 while (c[i] != \'\0\' || oper.top()!= \'\0\') 85 { 86 if (isNum(c,i)) 87 { 88 float sum = Num(c,i); 89 number.push(sum); 90 // cout << sum << endl; 91 if (c[i]!=\'\0\') 92 i++; // i自增前指向空格或者字符串终止符 93 continue; 94 } 95 switch(compare(oper.top(),c[i])) 96 { 97 case \'<\': 98 // 继续压栈 99 oper.push(c[i]); 100 i = i+1; 101 if (c[i]!=\'\0\') i++; 102 break; 103 case \'=\': 104 // 弹栈 105 oper.pop(); 106 i = i+1; 107 if (c[i]!=\'\0\') i++; 108 break; 109 case \'>\': 110 // 栈顶为优先级高的运算符，进行计算后压栈 111 char oper1 = oper.top(); 112 oper.pop(); 113 float num1 = number.top(); 114 number.pop(); 115 float num2 = number.top(); 116 number.pop(); 117 float ans = cal(num1,oper1,num2); 118 number.push(ans); 119 // 此时c[i]符号并没有压入栈中，所以不用i+2 120 121 } 122 } 123 printf("%.2f\n",number.top()); 124 } 125 126 return 0; 127 }
版权声明：本文为twomeng原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。