符號匹配

/*
	符號匹配是一種常見的算法問題，主要用于檢查給定的字符串中
	各種符號（如括號()、方括號[]、花括號{}等）是否正確配對和嵌套。
	在一個合法的符號序列中，每個左符號（如(、[、{）都必須有一個對應
	的右符號（如)、]、}），并且符號的嵌套順序必須正確。
	例如，{[()]} 是一個合法的符號序列，而 {[(])} 則不是，
	因為 [ 和 ] 的嵌套順序被打亂了。

	實現思路
	通常使用棧（Stack）這種數據結構來解決符號匹配問題。具體步驟如下：

	遍歷輸入的字符串。
	當遇到左符號時，將其壓入棧中。
	當遇到右符號時，檢查棧頂元素是否為對應的左符號。如果是，則將棧頂元素彈出；如果不是或者棧為空，則說明符號不匹配。
	遍歷結束后，如果棧為空，則說明所有符號都匹配；否則，說明有左符號沒有對應的右符號。
*/

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

// 函數用于檢查符號是否匹配
bool isMatchingPair(char opening, char closing) {
	if (opening == '(' && closing == ')') return true;
	if (opening == '[' && closing == ']') return true;
	if (opening == '{' && closing == '}') return true;
	return false;
}

// 函數用于檢查字符串中的符號是否匹配
bool isBalanced(const string& expression) {
	stack<char> s;
	for (char ch : expression) {
		if (ch == '(' || ch == '[' || ch == '{') {
			// 如果是左符號，將其壓入棧中
			s.push(ch);
		} else if (ch == ')' || ch == ']' || ch == '}') {
			if (s.empty()) {
				// 如果棧為空，說明沒有對應的左符號
				return false;
			} else {
				char top = s.top();
				s.pop();
				if (!isMatchingPair(top, ch)) {
					// 如果棧頂元素與當前右符號不匹配
					return false;
				}
			}
		}
	}
	// 遍歷結束后，如果棧為空，則說明所有符號都匹配
	return s.empty();
}

int main() {
	string expression = "{[()]}";
	if (isBalanced(expression)) {
		cout << "符號匹配" << endl;
	} else {
		cout << "符號不匹配" << endl;
	}
	return 0;
}