棧的應用--表達式括号比對

1353：表達式括号比對(stack)

題目連結：http://ybt.ssoier.cn:8088/problem_show.php?pid=1353

時間限制: 1000 ms 記憶體限制: 65536 KB

1. 題目描述

假設一個表達式有英文字母（小寫）、運算符（+，—，*，/）和左右小（圓）括号構成，以“@”作為表達式的結束符。請編寫一個程式檢查表達式中的左右圓括号是否比對，若比對，則傳回“YES”；否則傳回“NO”。表達式長度小于255，左圓括号少于20個。

【輸入】

一行資料，即表達式。

【輸出】

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

【輸入樣例】

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

【輸出樣例】

YES

【提示】

【樣例輸入2】

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

【樣例輸出2】

NO

【來源】

No

2. 代碼

#include<iostream>
#include<stack>
#include<string>
using namespace std;
string check_parenthese(string x)
{
	stack<char>count;
	while (x != "")
	{
		char m = x[0];
		if (m == '(')
			count.push('(');
		else if (m == ')')
		{
			if (count.size() == 0)
				return "NO";
			else
				count.pop();
		}
		x.erase(0, 1);
	}
	if (count.size() == 0)
		return "YES";
	else
		return "NO";
}
int main()
{
	string str;
	getline(cin, str,'@');
	cout << check_parenthese(str) << endl;
}
           

1354：括弧比對檢驗

題目連結：http://ybt.ssoier.cn:8088/problem_show.php?pid=1354

時間限制: 1000 ms 記憶體限制: 65536 KB

1. 題目描述

假設表達式中允許包含兩種括号：圓括号和方括号，其嵌套的順序随意，如（［ ］（））或［（［ ］［ ］）］等為正确的比對，［（ ］）或（［ ］（ ）或 ( ( ) ) ）均為錯誤的比對。

現在的問題是，要求檢驗一個給定表達式中的括弧是否正确比對？

輸入一個隻包含圓括号和方括号的字元串，判斷字元串中的括号是否比對，比對就輸出 “OK” ，不比對就輸出“Wrong”。輸入一個字元串：［（［］［］）］，輸出：OK。

【輸入】

輸入僅一行字元（字元個數小于255）。

【輸出】

比對就輸出 “OK” ，不比對就輸出“Wrong”。

【輸入樣例】

［（］）

【輸出樣例】

Wrong

【來源】

No

2. 代碼

#include<iostream>
#include<stack>
#include<string>
using namespace std;
bool check(string x)
{
	stack<char>count;
	while (x != "")
	{
		if (x[0] == '(' || x[0] == '[')
			count.push(x[0]);
		else 
			if (x[0] == ')')
			{
				if (count.size() != 0 && count.top() == '(')
				{
					count.pop();
				}
				else
					return 0;
			}
			else if (x[0] == ']')
			{
				if (count.size() != 0 && count.top() == '[')
				{
					count.pop();
				}
				else
					return 0;
			}
		x.erase(0, 1);
	}
	if (count.size() == 0)
		return 1;
	else 
		return 0;
}
int main()
{
	string s;
	getline(cin, s);
	if (check(s) == true)
		cout << "OK" << endl;
	else
		cout << "Wrong" << endl;
}