上课笔记(6)(1)——＃629. 表达式括号匹配(stack)

Description

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

Format

Input

一行数据，即表达式。

Output

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

Samples

输入数据 1

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

输出数据 1

YES

输入数据 2

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

输出数据 2

NO

Limitation

1s, 1024KiB for each test case.

题解：

运用的是栈，如果是左括号则压栈，如果是右括号则判断栈内是否有左括号，若有则将其与右括号一起弹栈，若不是则直接结束程序，因为有括号的前面是一定要有匹配的左括号的，最后在程序末尾处判断栈内是否有剩余的括号。

程序：

#include<bits/stdc++.h>
using namespace std;
char s[270],stk[30];
int tp;//栈顶指针，为0则栈为空； 
int main() {
	cin>>s;
	for(int i=0;s[i];i++){//遍历每个字符 
		if(s[i]=='(')
			stk[++tp]=')';//压栈
		if(s[i]==')'){
			if(tp==0){//栈为空，Game over! 
				cout<<"NO";
				return 0;
			}
			//栈不为空，存的是）
			tp--;//弹栈 
		} 
	} 
	if(tp)
		cout<<"NO";
	else
		cout<<"YES";
	return 0;
}