資料結構之棧的括号比對問題

問題描述

任意給定一個字元串，字元串中包含除了空格、換行符之外的任意字元。檢測字元串中的各類括号是否配對，即“(”與“)”、“［”與“］”、“｛”與“｝”是否比對。若比對輸出對應的比對個數。

輸入描述

一行字元串。

輸出描述

如果字元串中的括号比對，則輸出數字 1，并且在下一行輸出｛｝、［］、（）相對應的比對個數，否則輸出數字 0。

示例

輸入：

&()dgn*[{%}12]

輸出：

3

輸入：

12(%]{

輸出：

解題思路

這道題目在很多考研試卷中出過，或者是算法題，或者是簡答題。周遊字元串，遇到左括号進棧，遇到右括号則判斷是否與棧頂的左括号相比對，比對則棧頂元素出棧，否則跳過。

相關代碼

本題目直接使用C++中的棧（ s t a c k stack stack）類來解答，省去了 p o p pop pop和 p u s h push push等函數的自定義。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include<string>
#include <stack>
using namespace std;

int IsBracketMatching(string str)
{
	stack<char> s;
	int num = 0;
	for (int i = 0; i < str.size(); i++)// &()dgn*[{%}12]
	{
		if (str[i] == '(' || str[i] == '{' || str[i] == '[')
		{
			s.push(str[i]);
			continue;
		}
		if ((str[i] == ')' && s.top() == '(') || (str[i] == '}' && s.top() == '{') || (str[i] == ']' && s.top() == '['))
		{
			num++;
			s.pop();
		}
	}
	return num;
}

void main()
{
	string str;
	cout << "請輸入一行字元串，可包含[,{,(,),},]等字元" << endl;
	cin >> str; // &()dgn*[{%}12]
	int num = 0;
	num = IsBracketMatching(str);
	cout << num << endl;
	system("pause");
	return;
}
           

運作結果

1、

請輸入一行字元串，可包含[,{,(,),},]等字元

s(f[[{dfs}df]df]23)df

4

請按任意鍵繼續. . .

2、

請輸入一行字元串，可包含[,{,(,),},]等字元

&()dgn*[{%}12]

3

請按任意鍵繼續. . .