|
题目描述：
输入一个字符串比如{[(2+3)(1-3)] + 4}(14-3)，分析它的括号使用是否正确 括号有三种，小括号()，中括号[]，大括号{} 正确的括号使用必须满足以下条件（和数学上定义一致）： 1) 左右括号必须匹配 2) 每一种类型括号只能和同一类型的括号匹配，即（和）匹配 [和]匹配 {和}匹配 3) 括号有优先级，小括号在最内层，中括号必须嵌套在小括号外面，大括号必须嵌套的中 括号外面 4) 比如{}, ([])这样都是非法的 5) 除了最外层可以连续嵌套大括号外，小括号和中括号不能连续嵌套，比如(()), [[()]]都是 非法的，但是{{[()]}}是合法的 6) 不需要考虑除了括号之外的其他字符是否违反了数学上的规定
解决思路
先扫描一遍，去除除了括号外的字符，再对括号字符串进行优先级匹配和嵌套匹配，如果没错误，最后进行括号匹配。
具体代码
// Pinduoduo02.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include
#include
#include
#include
#include
using namespace std;
int priority(char ch)
{
switch (ch)
{
case '(':
return 1;
break;
case '[':
return 2;
break;
case '{':
return 3;
break;
default:
return 0;
break;
}
return 0;
}
bool match(char & a, char & b)
{
if ( (a == '(' && b == ')') || (a == '[' && b == ']') || (a == '{' && b == '}') )return true;
else return false;
}
bool analysis(string & str)
{
list bracket;
for (int i = 0; i < str.length(); ++i)
{
if (str[i] == '(' || str[i] == '[' || str[i] == '{' ||
str[i] == ')' || str[i] == ']' || str[i] == '}')bracket.push_back(str[i]);
}
if (bracket.size() % 2 != 0)return false;
list ::iterator it1 = bracket.begin();
list ::iterator it2 = bracket.begin(); ++it2;
for (; it2 != bracket.end(); ++it1, ++it2)
{
if (*it1 == '{' && *it2 == '}' || *it1 == '[' && *it2 == ']' ||
*it1 == '(' && *it2 == '(' || *it1 == '[' && *it2 == '['
)return false;//连续嵌套的判断;
else if( (*it2 == '{' && *it1 == '(') || (*it2 == '[' && *it1 == '(') ||
(*it2 == '{' && *it1 == '[') )return false;//优先级的判断;
}
list que;
it1 = bracket.begin();
for (; it1 != bracket.end(); ++it1)
{
switch (*it1)
{
case '{':
que.push_back(*it1);
break;
case '[':
que.push_back(*it1);
break;
case '(':
que.push_back(*it1);
break;
case ')':
if (que.back() == '(')que.pop_back();
else return false;
break;
case ']':
if (que.back() == '[')que.pop_back();
else return false;
break;
case '}':
if (que.back() == '{')que.pop_back();
else return false;
break;
default:
break;
}
}
if (que.empty())return true;
return false;
}
int main()
{
//string str = "{[(2+3)*(1-3)] + 4}*(14-3)";
string str = "{@@$[@#@(#34){}]@#@~!}sdff#f[..(dfasdfsdf)](){()}";
cout |