每日一练3

1.表达式括号匹配

题目描述

假设一个表达式有英文字母（小写）、运算符（+,—,,/+,—,∗,/）和左右小（圆）括号构成，以“@@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YESYES”；否则返回“NONO*”。表达式长度小于255255，左圆括号少于2020个。注意的是这里只用匹配括号数量即可！

输入格式

一行数据，即表达式。

输出格式

一行，即“YES”或“NO”。

样例1

输入数据 1

1
2*(x+y)/(1-x)@

输出数据 1

1
YES

样例2

输入数据 2

1
(25+x)*(a*(a+b+b)@

输出数据 2

1
NO
  • 考虑使用到的数据结构栈

当遇到 ( 左括号时入栈，遇到 ) 右括号时首先判断栈中是否有元素：

  • 如果没有则表明右括号在左括号之前所以表达式不合法
  • 当栈中有元素让栈中的元素出栈，运行到最后栈中如果为空时，则表明 () 是合法的，如果栈中如还有元素，则不合法则说明左括号与右括号并不一一对应

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<stack>
using namespace std;
int main(){
	stack<char>s;
	char num;
	int flag=0;
	cin>>num;
	while(num!='@'){
		if(num=='('){
			s.push(num);
		}
	 if(num==')'){
		if(s.empty()){
			cout<<"NO";//判断）在（的左边 
			flag=1;
			break;
		}
		else{
		s.pop();	
		}
	}
		cin>>num;	
	}
	// 
	if(flag==0&&s.empty()){
		cout<<"YES";
	}
	if(flag==0&&!s.empty()){// )括号少于(括号导致出栈的元素少于进栈的元素 
		cout<<"NO";
	}
	return 0;
	 
	
}

2.括号匹配问题

说明

在某个字符串（长度不超过100）中有左括号、右括号和大小写字母；规定（与常见的算数式子一样）任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序，找到无法匹配的左括号和右括号，输出原来字符串，并在下一行标出不能匹配的括号。不能匹配的左括号用”$”标注,不能匹配的右括号用”?”标注.

输入格式

输入包括多组数据，每组数据一行，包含一个字符串，只包含左右括号和大小写字母，字符串长度不超过100

注意：cin.getline(str,100)最多只能输入99个字符！

输出格式

对每组输出数据，!!!输出两行，第一行包含原始输入字符!!!，第二行由””,”?”和空格组成，””,”?”和空格组成，””和”?”表示与之对应的左括号和右括号不能匹配。

样例

输入数据 1

1
2
((ABCD(x)
)(rttyy())sss)(

输出数据 1

1
2
3
4
((ABCD(x)
$$
)(rttyy())sss)(
?            ?$

解题思路

  • 1、分析题目：每输入一行在下一行输出括号是否匹配
  • 2、与上一题方法类似可以使用stack来解决问题，即当输入的字符为 “(“ 时，入栈，在输入的字符为 “ ) ” 时，首先判断栈是否为空，如果栈为空则代表在有括号之前没有左括号，右括号不合法
  • 3、当进行完所有的运算符之后输出之前输入的字符以及在下一行输出判断括号是否匹配的$和？

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;
int main(){
    char str[107],mo[107];
    stack <int> s;
    while(cin>>str)
	{
        int l=strlen(str);
        for(int i=0;i<l;i++)
		{
            if(str[i]=='(')
			{ 
                s.push(i);
                mo[i]=' ';
            }   
        	else if(str[i]==')')
			{
                if(!s.empty())
				{
                    s.pop();
                    mo[i]=' ';
                }
                else
				{
                    mo[i]='?'; 
                }
            }
            else
			{ 
                mo[i]=' '; 
            }
        }
        while(!s.empty())
		{
            mo[s.top()]='$';
            s.pop();
        }
        puts(str);
        for(int i=0;i<l;i++)
		{
			printf("%c",mo[i]);
		}
		cout<<endl;   
		getchar();   
    }
    return 0;
}

3.十进制转M进制

说明

用递归算法将一个十进制数X转换成任意进制数M（2≤M≤36）。

输入格式

一行两个数，第一个十进制数X，第二个为进制M。

输出格式

输出结果（M进制数）。

样例

输入数据 1

1
31 16

输出数据 1

1
1F

提示

例如：31 16 ｛将十进制31转化为十六进制数｝

解题思路

  • 十进制转M进制的思路为：将十进制数除以M取余数后将余数进栈，全部除完后，求栈顶元素然后出栈
  • 对进栈的数进行字符处理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
#include<stack> 
using namespace std;
int main(){
	char arr[]="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";//字符处理
	stack <int> s;
	int a,b,m;
	cin>>a;
	cin>>b;
	while(a!=0){
		m=a%b;
		a=a/b;
		s.push(arr[m]);//余数对应的字符进栈
	}
	while(!s.empty()){
		char c;
		c=s.top();
	cout<<c;
	s.pop();	
	}
	return 0;
}

4.车厢调度

说明

​ 有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n<=1000），分别按照顺序编号为1，2，3，…，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。
负责车厢调度的工作人员需要知道能否使它以a1,a2,…,an的顺序从B方向驶出，请来判断能否得到指定的车厢顺序。
img

输入格式

第一行为一个整数n，其中n<=1000，
表示有n节车厢，第二行为n个数字，表示指定的车厢顺序。

输出格式

如果可以得到指定的车厢顺序，则输出一个字符串 ”YES”，否则输出”NO”（注意要大写，不包含引号）。

样例

输入数据 1

1
2
5
5 4 3 2 1

输出数据 1

1
YES

解题思路

  • 题目读来读出没理解他的意思，CSDN查了查。题目的大概意思是：进栈1,2,3…n 总共n个数。判断输入的数与出栈的数是否合法。
  • 输入的数有两个途径得到，一个是还没有入栈时的数即 b[i]=i ,这样不需要入栈，这个数是合法的。
  • 另一种是在栈顶的数，当栈不为空且栈顶元素与输入的数相等时，出栈
  • 当输入的数都经过了以上两个判断后栈中还有元素时，表明输入的这一串数不合法，反之则 YES

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<stack>
using namespace std;
const int N=1e5+7;
int b[N];//可以用i来代替A轨，就不用另开
stack <int> s;//C轨
int main(){
	int n;
	int t=1;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>b[i];
	if(b[t]!=i){
		s.push(i);
	}
	if(b[t]==i){
		t++;
	}
	while(!s.empty()&&s.top()==b[t]){
		s.pop();
		t++;
	}
	

	}
	if(s.empty()){
		cout<<"YES";
	}
	else{
		cout<<"NO";
	}
	return 0;
}