安庆建设机械网站萧山工程建设有限公司网站

1.表达式括号匹配(stack)

$Part$ $1$ 读题

题目描述

假设一个表达式有英文字母（小写）、运算符（$+$，$—$，$\times$，$÷$）和左右小（圆）括号构成，以“$@$”作为表达式的结束符。

请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“$YES$”；否则返回“$NO$”。表达式长度小于$255$，左圆括号少于$20$个。

输入格式

包括一行数据，即表达式

输出格式

包括一行，即“$YES$” 或“$NO$”。

输入样例1

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

输出样例1

YES

输入样例2

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

输出样例2

NO

数据范围与提示

表达式$S$的长度$\le 225$

$Part$ $2$ 思路

根据题意，我们知道了本题需要我们在输入后，找到字符串中的"$($“和”$)$“，然后进行计算，把”$($“放入栈中，每当出现一个”$)$"，就把栈顶减一，遇到结尾的$@$后，截止运算，判断栈顶是否为$0$，输出$YES$或$NO$

小tip：大家可以先根据思路，写一下代码哦！

$Part$ $3$ 代码

#include<bits/stdc++.h>
using namespace std;
int top;
int main(){string a; char s[3000];cin>>a;int n=a.size();for(int i=0;i<n;i++){if(a[i]=='(')s[++top]=1;if(a[i]==')'){if(s[top]==1&&top>0)s[--top]=0;else{cout<<"NO";break;}}if(a[i]=='@'){if(top==0)cout<<"YES";else cout<<"NO";}}return 0;
}

2.括弧匹配检验(check)

$Part$ $1$ 读题

题目描述

假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，如$([]())$或$[([][])]$等为正确的匹配，$[(])$或$([]()$或$(())))$均为错误的匹配。

现在的问题是，要求检验一个给定表达式中的括弧是否正确匹配？

输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出“$OK$” ，不匹配就输出“$Wrong$”。

输入格式

输入仅一行字符（字符个数$＜255$）

输出格式

匹配就输出 “$OK$” ，不匹配就输出“$Wrong$”。

输入样例

[(])

输出样例

Wrong

数据范围与提示

字符个数$n＜255$

$Part$ $2$ 思路

看到题目，大家可能认为与题目1相类似，仅仅是多了一个$[]$，但是尝试后发现并没有想象中的那么简单，所以我们举例分析：

字符$n$：$([)]$

下标$i$：$0123$

若$s[i]$是“$($”或是“$[$”就无条件进入栈$a$，将栈$a$下标 + + t o p ++top