1.案例分析

• 检验算法借助一个栈，每当读入一个左括号，则直接入栈，等待相匹配的同类右括号；每当读入一个右括号，若与当前栈顶的左括号类型相同，则二者匹配，将栈顶的左括号出栈，直到表达式扫描完毕在处理过程中，还要考虑括号不匹配出错的情况。

2.算法步骤

• ①初始化一个空栈S
• ②设置一标记性变flag，用来标记匹配结果以控制循环及返回结果，1表示正确匹配，0表示错误匹配，fag初值为1。
  ③扫描表达式，依次读入字符ch，如果表达式没有扫描完毕或flag非零，则循环执行以下操作:
  • 若ch是左括号“[”或“("，则将其压入栈；
  • 若ch是右括号“)”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是“(”，则正确匹配，否则错误匹配，fag置为0；
  • 若ch是右括号“]”，则根据当前栈顶元素的值分情况考虑：若栈非空且栈顶元素是"[",则正确匹配，否则错误匹配，flag置为0。
• ④退出循环后，如果栈空且fag值为1，则匹配成功，返回true,否则返回false

3.算法描述

bool Matching() 
{stack<char> s;  // 定义一个stack容器char ch, temp;int flag = 1;     // 标记匹配结果以控制循环及返回结果cin >> ch; //读入第一个字符while (ch != '#' && flag) //假设表达式以“#”结尾{switch (ch){case '[':case '(':      // 若是左括号，则将其压入栈s.push(ch);break;case ')':  //若是“)”，则根据当前栈顶元素的值分情况考虑if (!s.empty() && s.top() == '(')  // 若栈非空且栈顶元素是“(”，则正确匹配{temp = s.top();s.pop();}		                           elseflag = 0;    // 若栈空或栈顶元素不是“(”，则错误失败break;case ']': //若是“]”，则根据当前栈顶元素的值分情况考虑if (!s.empty() && s.top() == '[') // 若栈非空且栈顶元素是“[”，则正确匹配{temp = s.top();s.pop();}		                          elseflag = 0;         //若栈空或栈顶元素不是“[”，则错误匹配break;} //switchcin >> ch; //继续读入下一个字符} //whileif (s.empty() && flag)return true;         // 匹配成功elsereturn false;      // 匹配失败
}

4.代码实现

• main.cpp

#include <iostream>
#include <cstdlib>
#include <stack>using namespace std;bool Matching() 
{stack<char> s;  // 定义一个stack容器char ch, temp;int flag = 1;     // 标记匹配结果以控制循环及返回结果cin >> ch; //读入第一个字符while (ch != '#' && flag) //假设表达式以“#”结尾{switch (ch){case '[':case '(':      // 若是左括号，则将其压入栈s.push(ch);break;case ')':  //若是“)”，则根据当前栈顶元素的值分情况考虑if (!s.empty() && s.top() == '(')  // 若栈非空且栈顶元素是“(”，则正确匹配{temp = s.top();s.pop();}		                           elseflag = 0;    // 若栈空或栈顶元素不是“(”，则错误失败break;case ']': //若是“]”，则根据当前栈顶元素的值分情况考虑if (!s.empty() && s.top() == '[') // 若栈非空且栈顶元素是“[”，则正确匹配{temp = s.top();s.pop();}		                          elseflag = 0;         //若栈空或栈顶元素不是“[”，则错误匹配break;} //switchcin >> ch; //继续读入下一个字符} //whileif (s.empty() && flag)return true;         // 匹配成功elsereturn false;      // 匹配失败
}int main() 
{cout << "请输入待匹配的表达式，以“#”结束：" << endl;//int flag = (int)Matching();if (Matching())cout << "括号匹配成功！" << endl;elsecout << "括号匹配失败！" << endl;system("pause");return 0;
}

Leetcode 20题代码

class Solution {
public:bool isValid(string s){stack<char> S;  // 定义一个stack容器char temp;int flag = 1;int i = 0;// 标记匹配结果以控制循环及返回结果 while (s[i] != '\0'&& flag){switch (s[i]){case '[':case '(':case '{':          // 若是左括号，则将其压入栈S.push(s[i]);break;case ')':  //若是“)”，则根据当前栈顶元素的值分情况考虑if (!S.empty() && S.top() == '(')  // 若栈非空且栈顶元素是“(”，则正确匹配{temp = S.top();S.pop();}elseflag = 0;    // 若栈空或栈顶元素不是“(”，则错误失败break;case ']': //若是“]”，则根据当前栈顶元素的值分情况考虑if (!S.empty() && S.top() == '[') // 若栈非空且栈顶元素是“[”，则正确匹配{temp = S.top();S.pop();}elseflag = 0;         //若栈空或栈顶元素不是“[”，则错误匹配break;case '}': //若是“]”，则根据当前栈顶元素的值分情况考虑if (!S.empty() && S.top() == '{') // 若栈非空且栈顶元素是“{”，则正确匹配{temp = S.top();S.pop();}elseflag = 0;         //若栈空或栈顶元素不是“[”，则错误匹配break;} //switchi++;} //whileif (S.empty() && flag)return true;         // 匹配成功elsereturn false;      // 匹配失败}
};

• 运行结果