Задача: перевірка скобового вираження

Є текстовий рядок, яка містить довільне Дужковий вираз (дужки (), [], или {}). Необхідно створити функцію check(), яка буде перевіряти це Дужковий вираз на правильність:

перевірка(“і(x)”) -> true
перевірка(“[(]”) -> false
перевірка(“[{}]”) -> true
перевірка(“)(“) -> false
перевірка(“”) -> true
перевірка(“b([{}-()]{a})”) -> true

З рішенням потрібно повозитися. Але коли воно знайдеться – буде коротким і компактним (10 – 15 строк). Варіантів рішень може бути багато.

Рішення

Перший варіант:

#include <iostream>
using namespace std;

const char *delim[2] = { "([{", ")]}" };

bool check(const string& s)
{
	string stack = "";
	for (int i = 0; i < s.size(); i++) {
		const char c = s[i];
		if (strchr(delim[0], c) != NULL) {
			stack.push_back(c);
			continue;
		}
		const char *z;
		if (NULL == (z = strchr(delim[1], c)))
			continue;
		if (stack.empty() || stack.back() != delim[0][z - delim[1]])
			return false;
		stack.pop_back();
	}
	return stack.empty();
}

int main()
{
	cout << check("(2 + 2) * 4") << endl;
	cout << check("(2 + 2( * 4") << endl;
	cout << check("{}") << endl;
	cout << check("]8[") << endl;
}

#include <iostream>

using namespace std;

const char *delim[2] = { "([{", ")]}" };

bool check(const string& s)

{

string stack = "";

for (int i = 0; i < s.size(); i++) {

const char c = s[i];

if (strchr(delim[0], c) != NULL) {

stack.push_back(c);

continue;

}

const char *z;

if (NULL == (z = strchr(delim[1], c)))

continue;

if (stack.empty() || stack.back() != delim[0][z - delim[1]])

return false;

stack.pop_back();

}

return stack.empty();

}

int main()

{

cout << check("(2 + 2) * 4") << endl;

cout << check("(2 + 2( * 4") << endl;

cout << check("{}") << endl;

cout << check("]8[") << endl;

}

Другий варіант:

#include <iostream>
#include <vector> 
using namespace std;

const char *delim[2] = { "([{", ")]}" };

bool check(const char* p) {
	vector<char> stack(0);
	for (; *p != '\0'; p++) {
		if (strchr(delim[0], *p) != NULL) {
			stack.push_back(*p);
			continue;
		}
		const char *z;
		if (NULL == (z = strchr(delim[1], *p)))
			continue;
		if (stack.empty() ||
			stack.back() != delim[0][z - delim[1]])
			return false;
		stack.pop_back();
	}
	return stack.empty();
}

int main()
{
	cout << check("(2 + 2) * 4") << endl;
	cout << check("(2 + 2( * 4") << endl;
	cout << check("{}") << endl;
	cout << check("]8[") << endl;
}

#include <iostream>

#include <vector>

using namespace std;

const char *delim[2] = { "([{", ")]}" };

bool check(const char* p) {

vector<char> stack(0);

for (; *p != '\0'; p++) {

if (strchr(delim[0], *p) != NULL) {

stack.push_back(*p);

continue;

}

const char *z;

if (NULL == (z = strchr(delim[1], *p)))

continue;

if (stack.empty() ||

stack.back() != delim[0][z - delim[1]])

return false;

stack.pop_back();

}

return stack.empty();

}

int main()

{

cout << check("(2 + 2) * 4") << endl;

cout << check("(2 + 2( * 4") << endl;

cout << check("{}") << endl;

cout << check("]8[") << endl;

}

результат однаковий:

Перший варіант:

[crayon-67418b57ed242163012161/]

Другий варіант:

[crayon-67418b57ed24b976999690/]

результат однаковий:

13 думки про "Задача: перевірка скобового вираження”

Programmer_blog говорить:
03.09.2015 at 10:33
string str("{}{}{}"); int bct1, bct2, bct3; bool is_correct(true); for (auto c : str) { do { if (c == "(") { ++bct1; break; } if (c == ")") { --bct1; break; } if (c == "{") { ++bct2; break; } if (c == "}") { --bct2; break; } if (c == "[") { ++bct3; break; } if (c == "]") { --bct3; break; } } while (false); if (bct1 < 0 || bct2 < 0 || bct3 < 0) { is_correct = false; break; } } cout << (is_correct == false || bct1 || bct2 || bct3 ? "false" : "true");
Типу того (код не перевіряв, можуть бути помилки). BLE будь- різно прикрашати і робити гнучкіше, но суть та же, що і в разі одного виду дужок – блок-схема алгоритму є тут: http://pro-prof.com/archives/578
відповісти
Olej говорить:
03.09.2015 at 14:03
> код не перевіряв
А даремно ;-) …
1. замість цього, якщо (з == “(“) має if (з == «(«)
ну і у всіх подібних гілках…
(і то якщо тільки це компілювати з опціями стандарту C ++ 11)
2. але і це не буде працювати без:
int bct1 = 0, bct2 = 0, bct3 = 0;
принаймні, доти, поки це (bct1, bct2, bct3) – локальні змінні.
3. і, нарешті, це ніколи не буде працювати просто алгоритмічно, бо ось таке Дужковий вираз теж буде абсолютно коректним:
string str( "( 1 [ 2 { 3 ) 4 ] }");
відповісти
1. Programmer_blog говорить:
  04.09.2015 at 18:55
  >> бо ось таке Дужковий вираз теж буде абсолютно коректним: ( 1 [ 2 { 3 ) 4 ] }
  Я не вважаю такий вислів коректним. В умовах задачі написано “перевіряти на правильність”. “правильність” ви ніяк не формалізували, наведені в завданні приклади не містять начебто жодної групи дужок, всередині якої порушується баланс інших дужок. Ну і взагалі, не зрозуміло що саме задається (може здаватися) різними видами дужок.
  З лапками і инициализацией змінних я накосячілі, да. Ще конструкцію do while(false) я тут даремно застосував, профіту з неї в цьому випадку не буде.
  Приведи своє рішення зі стеками, цікаво подивитися (я по твоєму опису профіту з них не бачу).
  відповісти
  1. Olej говорить:
    05.09.2015 at 11:49
    > Я не вважаю такий вислів коректним.
    Ось і я не вважаю.
    А код показаний – вважає. ;-)
  2. Olej говорить:
    05.09.2015 at 11:51
    > Приведи своє рішення зі стеками, цікаво подивитися
    А воно з 1-го для лежить під спойлером “Рішення”.
    І навіть не одне рішення…
  3. Olej говорить:
    05.09.2015 at 12:22
    > Ну і взагалі, не зрозуміло що саме задається (може здаватися) різними видами дужок.
    Що таке правильне Дужковий вираз (і для різних видів дужок теж) діти вчать у 4-му класі початкової школи.
Olej говорить:
03.09.2015 at 14:15
Взагалі то, це в закамуфльованій формі завдання обчислення вкладених дужкових виразів (як, например, в LISP lambda-виразів … або в калькуляторі), але спеціально в дуже упрщённой формулюванні. У загальному вигляді задача таких обчислень вирішується рекурсивно: при відкритті чергового скобового вираження – заштовхуємо параметри в стек і викликаємо нижній рівень рекурсії, а при завершенні обробки скобового рівня – повернення з рекурсивного виклику і виштовхування переметров і стека назад.
Але в такому формулюванні завдання обчислення на рівні рекурсії вироджене (нічого не робити), тому рекурсія відпала, а стек залишився.
відповісти
андрей говорить:
26.04.2016 at 17:03
Я хочу розробити програму комп'ютерна діагностики аудіо відео радіо апаратури опис програми там є віконце де можна писати пишемо того що будемо перевіряти і програма знає всі параметри радіо деталь в савляем щупи в Вуков карту і перевіряємо радіо деталі якщо горить зеленим кольором то радіо деталь робоча якщо горить жовтим то радіо деталь підлозі робоча тобто промені поміняти якщо горить червоним то радіо деталь не рабочая.Нужна помочт раработки?
відповісти
1. Olej говорить:
  26.04.2016 at 17:25
  1. це буде дуже непроста за кодом і розміром програма
  2. просто зі входу звукової карти (мікрофонний?) так перевірити не вийде – це вхід АЦП, на нього можна подавати напруга, але без внешнего джерела напруги підключати туди “радіодеталей” безглуздо…
  3. навіть вирішивши питання з джерелом напруги, так перевіряти параметри ви зможете далеко не всіх найпростіших радіодеталей: діода, деяких резисторів … транзистор ви вже не перевірите, не кажучи вже про більш складних пристроях.
  4. така програма (навіть якби ви її попри всі обмеження можливостей зробили) будет залежною від операційної системи: працює під Windows не буде працювати під Linux, якщо ви зробите під Linux – вона не буде працювати під FreeBSD, зробите під FreeBSD – не працюватиме під Solaris і т.д.
  У мережі є досить багато програм комп'ютерних осцилографів, підключаються до входу аудіокарти. Багато з них – з відкритим кодом. Візьміть код таких програм і дивіться як вони працюють з аудиовходом.
  відповісти
Олексій говорить:
06.06.2016 at 22:18
#include "stdafx.h" #include #include #include
using namespace std;
bool check(char*, int = 0, int = 0);
int main() { cout<<boolalpha<<setw(17)<<"y(x) "<<check("y(x)",4)<<endl <<setw(17)<<"[(] "<<check("[(]",3)<<endl <<setw(17)<<"[{}] "<<check("[{}]",4)<<endl <<setw(17)<<")( "<<check(")(",2)<<endl <<setw(17)<<""<<check("")<<endl <<setw(17) << "b([{}-()]{a}) " << check("b([{}-()]{a})", 13) << endl <<setw(17)<<"(1[2{3)4]} "<<check("(1[2{3)4]}",10)<<endl;
_getch(); return 0; }
bool check(char* str, int finish, int start) { char chArray[] = "({[)}]"; bool result = true; int mult = 0;
for (int i = start; i<finish; i++) for (int q = 0; q<3; q++) if (str[i] == chArray[q]){ result = false; for (int f = i + 1; f < finish; f++) if (str[f] == chArray[q + 3]){ if (mult == 0){ result = check(str,f,(i+1)); if (!result) return false; break;} mult--;} else if (str[f] == chArray[q]) mult++;} return result; }
відповісти
Олексій говорить:
21.11.2017 at 09:02
Я програміст С ++ і можливо код буде громіздкий, але як вийшло.
#include "stdafx.h" #include #include
using namespace std;
//check(“y(x)”) -> true //check(“[(]”) -> false //check(“[{}]”) -> true //check(“)(“) -> false //check(“”) -> true //check(“b([{}-()]{ a })”) -> true
bool findclose(const string &data, char find = '\0', int ind = 0) { bool res = false;
if (find == '\0') return false;
for (int i = ind; i < data.length(); i++) { if (data[i] == find) return true; else { switch (data[i]) { case '{': res = findclose(data, '}', i + 1); if (res == false) return false; break; case '(': res = findclose(data, ')', i + 1); if (res == false) return false; break; case '[': res = findclose(data, ']', i + 1); if (res == false) return false; break; default: break; } } } return res; }
int main() { setlocale(LC_ALL, "Rus");
string data; char repeat = 'N'; do { cout << "==============================================" << endl; cout << "Введите строку проверки скобочного выражения: " <> data;
bool res = false;
for (int i = 0; i < data.length(); i++) { if (data[i] == '{' || data[i] == '(' || data[i] == '[') { switch (data[i]) { case '{': res = findclose(data, '}', i + 1); break; case '(': res = findclose(data, ')', i + 1); break; case '[': res = findclose(data, ']', i + 1); break; default: break; } break; } }
if (res) cout << "OK" << endl; else cout << "ERROR" << endl;
cout << "Повторить проверку? (Y-да, N-нет): " <> repeat;
} while (repeat == 'Y' || repeat == 'y');
system("pause"); return 0; }
відповісти
Вероніка говорить:
27.11.2017 at 13:36
Вітаю. Допоможіть, будь ласка. Розпишіть як працює кожен рядок в рішенні (перший варіант).
відповісти
Михайло говорить:
27.07.2020 at 16:55
Уповноважений c #:
за допомогою System;
простір імен Домашнє завдання5
{
клас Програма
{
статична перевірка буля(рядок тексту)
{
int count = 0;
char[] пам'ять = новий символ[100];
для кожного (Елемент символу в тексті)
{
switch (елемент)
{
справа{«: пам'ять[++count] = елемент; break;
справа(«: пам'ять[++count] = елемент; break;
справа[«: пам'ять[++count] = елемент; break;
справа}': if (пам'ять[count] == ‘{«) { count–; } else { повернення помилковим; }; break;
справа)': if (пам'ять[count] == ‘(«) { count–; } else { повернення помилковим; }; break;
справа]': if (пам'ять[count] == ‘[«) { count–; } else { повернення помилковим; }; break;
}
}
кількість повернень == 0 ? true : false;
}
статична порожнеча Головна(string[] аргументи)
{
Console.WriteLine(перевірка(Console.ReadLine()));
Console.ReadKey(true);
}
}
}
відповісти

Задача: перевірка скобового вираження

13 думки про "Задача: перевірка скобового вираження”

залишити коментар Скасувати відповідь

Останні повідомлення

недавні коментарі

Статистика