C++: проверить правильность расстановки скобок в строке

Учебная задачка, чтобы не потерялась...

Дана строка, в которой расставлены круглые скобки. Проверить правильность их расстановки.

Если скобки только круглые, наверное, можно вот так:

#include <iostream>
#include <string>
using namespace std;
 
int bracketCount (string s) {
    int len = s.length();
    int cnt = 0;
    char last = '0';
    for (int i=0; i<len; i++) {
        if (s[i]=='(') {
            cnt++; last = '(';
        }
        else if (s[i]==')') {
         if (cnt) {
             cnt--;
             if (last!='(' && last!=')') return -1;
         }
         else return -1;
         last = ')';
        }
    }
    return cnt;
}
 
int main () {
    string s1 ("())((in)Correct(br(ack)ets)");
    cout << endl << s1 << ":" << bracketCount(s1);
    string s2 ("Correct(br(ack)ets)");
    cout << endl << s2 << ":" << bracketCount(s2);
    system("pause>nul"); return 0;
}

Любой ответ, не равный нулю означает "неправильно расставлены".

Если задача банальней и корректные вложения скобок неважны, то есть, )()( тоже правильно, хватит и функции

int bracketCount (string s) {
    int len = s.length();
    int cnt = 0;
    for (int i=0; i<len; i++)
        if (s[i]=='(') cnt++;
        else if (s[i]==')') cnt--;
    return cnt;
}

Если делать с STL и стеком, возможно решение вида

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

int correctBrackets(string str) {
	stack <int> stack;
	char left = '(', right = ')';
	int err = 0;
	for (unsigned i = 0; i < str.size() && !err; ++i) {
		if (str[i] == left) stack.push(i);
		else if (str[i] == right) {
			if (stack.size() > 0) stack.pop();
			else err = -1;
		}
	}
	if (!err && stack.size() > 0) err = -1;
	return err;
}

int main(int argc, char** argv) {
	string s1("())((in)Correct(br(ack)ets)");
	cout << endl << s1 << ":" << correctBrackets(s1);
	string s2("Correct(br(ack)ets)");
	cout << endl << s2 << ":" << correctBrackets(s2);
	system("pause>nul"); return 0;
}

Это, с виду, легче модифицировать, проверяя вместо str[i] == left вхождение str[i] в строку допустимых левых скобок, например, "({[", ну, и с правыми так же.

17.05.2017, 21:59 [9836 просмотров]