自己写的一个单栈括号匹配，支持干扰字符

源自：4-4 栈应用括号匹配二

自己写的一个单栈括号匹配，支持干扰字符

#include <iostream>
#include "Stack.h"

using std::string;
using std::cout;
using std::endl;

/**
 * 检测字符串中的括号是否匹配
 * @param str 待检测匹配的字符串
 * @param tps1 匹配的符号
 * @param tps2 与tps1相匹配且顺序一致的符号
 * @return 括号是否匹配的布尔值
 */
bool isPaired(string str, string tps1, string tps2);

int main() {
    string s = "int main(){func(){while(true){cout << endl}}}";    //待检测字符串
    string msg;
    msg = isPaired(s, "({[", ")}]") ? "OK" : "No";
    cout << msg << endl;
    return 0;
}

bool isPaired(string str, string tps1, string tps2) {
    Stack<char> stack(str.length() / 2);  //如果字符串中的括号匹配，最差情况下栈需要的长度等于字符串长度的一半
    int tps_pos;
    char tmp;
    for (char i : str) {
        if (tps1.find(i) != -1) {   //栈存储字符串中的左括号
            if (stack.isFull())
                return false;
            stack.push(i);
        } else if ((tps_pos = tps2.find(i)) != -1) {
            if (stack.isEmpty())
                return false;
            stack.pop(tmp);
            if (tps1[tps_pos] != tmp) {    //判断字符串的某一右括号字符对应匹配的左括号是否与当前pop出的元素是否一致
                return false;
            }
        }
    }
    return stack.isEmpty(); //判断是否栈空，如果栈为空则说明匹配完毕，如果未空则说明有括号未匹配
}

好吧，这不是一个提问。只是一个代码片段分享，评论区不支持语法高亮就发问答区了。

提问者：Secnull 2016-10-04 23:26

个回答

黑巫师0: 2016-12-25 14:30:16

我也来分享一下，兄弟不会介意吧。和你写的有点不同，也支持干扰字符！

MyStack<char> *pStack = new MyStack<char>(30);
 int flag = 0;
 char elem;
 char str[] = "[cfg(2sdf*2ds)f]";
 for (int i = 0;i < strlen(str);i++)
 {
  switch (str[i])
  {
  case '(':
  case '[':
   pStack->push(str[i]);
   break;
  case ')':  
   if (!pStack->pop(elem))
   {
    flag = 1;
    continue;
   }
   if (elem != '(')
   {
    flag = 1;
   }
   break;
  case ']':
   if (!pStack->pop(elem))
   {
    flag = 1;
    continue;
   }
   if (elem != '[')
   {
    flag = 1;
   }
   break;
  }
 }
 if (!pStack->stackEmpty() || 1 == flag)
 {
  cout << "字符串括号不匹配" << endl;
 }
 else
 {
  cout << "字符串括号匹配" << endl;
 }

qq_第天堂_03899060

2016-10-13 16:17:30

#include <iostream>
#include "Stack.h"

using std::string;
using std::cout;
using std::endl;

/**
* 检测字符串中的括号是否匹配
* @param str 待检测匹配的字符串
* @param tps1 匹配的符号
* @param tps2 与tps1相匹配且顺序一致的符号
* @return 括号是否匹配的布尔值
*/
bool isPaired(string str, string tps1, string tps2);

int main() {
    string s = "int main(){func(){while(true){cout << endl}}}";    //待检测字符串
    string msg;
    msg = isPaired(s, "({[", ")}]") ? "OK" : "No";
    cout << msg << endl;
    return 0;
}

bool isPaired(string str, string tps1, string tps2) {
    Stack<char> stack(str.length() / 2);  //如果字符串中的括号匹配，最差情况下栈需要的长度等于字符串长度的一半
    int tps_pos;
    char tmp;
    for (char i : str) {
        if (tps1.find(i) != -1) {   //栈存储字符串中的左括号
            if (stack.isFull())
                return false;
            stack.push(i);
        } else if ((tps_pos = tps2.find(i)) != -1) {
            if (stack.isEmpty())
                return false;
            stack.pop(tmp);
            if (tps1[tps_pos] != tmp) {    //判断字符串的某一右括号字符对应匹配的左括号是否与当前pop出的元素是否一致
                return false;
            }
        }
    }
    return stack.isEmpty(); //判断是否栈空，如果栈为空则说明匹配完毕，如果未空则说明有括号未匹配
}

1