题单二总结DAY03

---

学习内容

1.P1739 表达式括号匹配
2.P4387 【深基15.习9】验证栈序列
3.P1449 后缀表达式

---

一、题目

P1739 表达式括号匹配

题目描述

假设一个表达式有英文字母（小写）、运算符（+、-、*、/）和左右小（圆）括号构成，以 @ 作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则输出 YES；否则输出 NO。表达式长度小于 $255$，左圆括号少于 $20$ 个。

输入格式

一行：表达式。

输出格式

一行：YES 或 NO。

输入输出样例 #1

输入 #1

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

输出 #1

YES

输入输出样例 #2

输入 #2

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

输出 #2

NO

说明/提示

表达式长度小于 $255$，左圆括号少于 $20$ 个。

Tips

栈里面放（）配对就行 （肯定 比）先入队

完整代码

#include<bits/stdc++.h>
using namespace std;
string s ="";
stack<char> a;
int main(){
	cin>>s;
	for(char ch: s){
		if(ch == '(') a.push(ch);
		else if(ch == ')'){
			if(a.empty()) {
				cout<<"NO";
				return 0; 
			}else {
				a.pop();
			}
		}else if (ch =='@') break;
			
		}
		
	
	
	if(a.empty()){
		cout<<"YES";
	}else{
		cout<<"NO";
	}
	
	return 0;
}

P4387 【深基15.习9】验证栈序列

题目描述

给出两个序列 pushed 和 poped 两个序列，其取值从 $1$ 到 $n(n\le 100000)$。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。请注意，给定的序列一定是一个排列（即没有重复数字）。

为了防止骗分，每个测试点有多组数据，不超过 $5$ 组。

输入格式

第一行一个整数 $q$，询问次数。

接下来 $q$ 个询问，对于每个询问：

第一行一个整数 $n$ 表示序列长度；

第二行 $n$ 个整数表示入栈序列；

第三行 $n$ 个整数表示出栈序列；

输出格式

对于每个询问输出答案。

输入输出样例 #1

输入 #1

2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3

输出 #1

Yes
No

Tips

记得用栈存就行了

完整代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int q;
	scanf("%d",&q);
	while(q--){
		int x =0;
		scanf("%d",&x);
		vector<int>c(x);
		vector<int>d(x);
		for(int i =0;i<x;i++){
			scanf("%d", &c[i]);
		}
		for(int i =0;i<x;i++){
			scanf("%d", &d[i]);
		}
		stack<int>a;
		int i=0,j =0;
		while(i<x && j<x ){
			a.push(c[i]);
			i++;
			while(!a.empty()&& a.top() == d[j]){
				a.pop();
				j++; 
			}	
		}
		if(a.empty()){
			printf("Yes\n");
		}else{
			printf("No\n");
		} 
		
	}
	return 0;
}

P1449 后缀表达式

题目描述

所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。

本题中运算符仅包含 $\text{+-*/}$。保证对于 $\text{/}$ 运算除数不为 0。特别地，其中 $\text{/}$ 运算的结果需要向 0 取整（即与 C++ / 运算的规则一致）。

如：$\text{3*(5-2)+7}$ 对应的后缀表达式为：$\text{3.5.2.-*7.+@}$。在该式中，@ 为表达式的结束符号。. 为操作数的结束符号。

输入格式

输入一行一个字符串 $s$，表示后缀表达式。

输出格式

输出一个整数，表示表达式的值。

输入输出样例 #1

输入 #1

3.5.2.-*7.+@

输出 #1

16

输入输出样例 #2

输入 #2

10.28.30./*7.-@

输出 #2

-7

说明/提示

数据保证，$1\le |s|\le 50$，答案和计算过程中的每一个值的绝对值不超过 $10^9$。

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	string s;	stack<int>st;	int num =0;
	bool flag =true;
	cin>>s; 
		for(char c :s){
			if(c>='0'&&c<='9'){
				num = num*10+(c-'0');
				flag =true;
			}else if(c == '.'){
				st.push(num);
				num =0;
				flag = false;		
			}else if(c == '+'||c == '-'|| c == '*'||c == '/'){
				int b = st.top();st.pop();
				int a = st.top();st.pop();
				int r =0;
				if(c=='+') r = a+b;
				else if(c=='-') r =a-b;
				else if(c=='*') r =a*b;
				else r=a/b;
				st.push(r);
			}else if(c=='@') break;
		}
		cout<<st.top();
	return 0;
}