机试指南 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] !='')
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] = '';
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
机试指南 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 }
机试指南 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 }
