括号匹配问题：栈的巧妙应用与代码优化【栈、优化、哈希表】

当解决算法问题时，灵活使用数据结构是至关重要的。在这个问题中，我们需要判断一个只包含括号的字符串是否有效，即括号是否能够正确匹配和闭合。使用栈这一数据结构可以很好地解决这个问题。

题目链接：有效的括号

解题思路：为什么使用栈？

括号匹配问题需要判断输入的字符串中的括号是否正确闭合，而且要求括号的顺序也必须正确。这种情况下，我们可以使用堆栈来处理。

堆栈是一种后进先出（LIFO）的数据结构，非常适合用来解决括号匹配问题。

当我们遇到左括号时，将其压入堆栈中，而遇到右括号时，我们可以弹出堆栈顶部的元素并比较是否匹配。

原始代码

首先，让我们来看一下最初的解答代码：

class Solution {
public:bool isValid(string ex) {stack<char> s;for(char c : ex){if(c == '(' || c == '[' || c == '{'){s.push(c);}else{if(s.empty()){return false;}else{if(c == ')' && s.top() == '('){s.pop();}else if(c == '}' && s.top() == '{'){s.pop();}else if(c == ']' && s.top() == '['){s.pop();}else {return false;}}}}return s.empty();}
};

优化的代码

为了简化逻辑并提高代码的可读性，我们可以使用哈希表来存储括号的对应关系，并结合栈的基本操作进行改进：

class Solution {
public:bool isValid(string s) {stack<char> st;unordered_map<char, char> mapping = {{')', '('},{']', '['},{'}', '{'}};for (char c : s) {if (c == '(' || c == '[' || c == '{') {st.push(c);} else {if (st.empty() || st.top() != mapping[c]) {return false;}st.pop();}}return st.empty();}
};

栈的基础操作的使用技巧

在解决这个问题时，我们充分利用了栈的基础操作：

1. push：将左括号入栈。
2. pop：遇到右括号时，出栈并与当前右括号比较是否匹配。
3. top：检查栈顶元素是否与当前右括号匹配。

这些操作使得我们能够高效地检查括号是否匹配。

总结与反思

括号匹配问题是一个典型的使用堆栈解决的问题。通过将左括号压入堆栈，然后在遇到相应的右括号时进行出栈匹配，我们可以有效地判断括号是否正确闭合。

原始代码虽然已经完成了任务，但存在着冗长的 if-else 语句，不够优雅。通过使用哈希表存储括号对应关系，我们能够用更简洁的代码完成同样的功能，提高代码的可读性和维护性。

括号匹配问题只是栈在算法中的一个小应用，栈还有许多其他强大的用途，如逆波兰表达式求值、深度优先搜索等。掌握栈的基本操作和灵活应用，对于提升算法和数据结构的理解能力非常有帮助。