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

13 thoughts on “Задача: проверка скобочного выражения”

1. 
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");


   Типа того (код не проверял, могут быть опечатки). Можно всяко- разно украшать и делать гибче, но суть та же, что и в случае одного вида скобок – блок-схема алгоритма есть тут: http://pro-prof.com/archives/578

   Ответить

2. > код не проверял
   А напрасно ;-) …

   1. вместо if (c == “(“) должно if (c == ‘(‘)
   ну и во всех подобных ветках…
   (и то если только это компилировать с опциями стандарта C++11)

   2. но и это не будет работать без:
   
int bct1 = 0, bct2 = 0, bct3 = 0;

   по крайней мере, до тех пор, пока это (bct1, bct2, bct3) – локальные переменные.

   3. и, наконец, это никогда не будет работать просто алгоритмически, потому что вот такое скобочное выражение тоже будет совершенно корректным:
   
string str( "( 1 [ 2 { 3 ) 4 ] }");


   Ответить

   1. >> потому что вот такое скобочное выражение тоже будет совершенно корректным: ( 1 [ 2 { 3 ) 4 ] }

      Я не считаю такое выражение корректным. В условиях задачи написано “проверять на правильность”. “правильность” вы никак не формализовали, приведенные в задаче примеры не содержат вроде бы ни одной группы скобок, внутри которой нарушается баланс других скобок. Ну и вообще, не понятно что именно задается (может задаваться) разными видами скобок.

      С кавычками и инициализацией переменных я накосячил, да. Еще конструкцию do while(false) я тут зря применил, профита с нее в этом случае не будет.

      Приведи свое решение со стеками, интересно посмотреть (я по твоему описанию профита с них не вижу).

      Ответить

      1. > Я не считаю такое выражение корректным.
         Вот и я не считаю.
         А код показанный – считает. ;-)

      2. > Приведи свое решение со стеками, интересно посмотреть
         А оно с 1-го для лежит под спойлером “Решение”.
         И даже не одно решение…

      3. > Ну и вообще, не понятно что именно задается (может задаваться) разными видами скобок.

         Что такое правильное скобочное выражение (и для разных видов скобок тоже) дети учат в 4-м классе начальной школы.

3. Вообще то, это в закамуфлированной форме задача вычисления вложенных скобочных выражений (как, например, в LISP lambda-выражений … или в калькуляторе), но специально в очень упрщённой формулировке. В общем виде задача таких вычислений решается рекурсивно: при открытии очередного скобочного выражения – заталкиваем параметры в стек и вызываем нижний уровень рекурсии, а при завершении обработки скобочного уровня – возврат из рекурсивного вызова и выталкивание переметров и стека обратно.
   Но в такой формулировке задачи вычисление на уровне рекурсии вырожденное (ничего не делать), поэтому рекурсия отпала, а стек остался.

   Ответить

4. Я хочу разработать программу компютерная диагностики аудио видео радио аппаратуры описание программы там есть окошко где можно писаить пишем того что будем проверять и программа знает все параметры радио деталь в савляем щупы в вуковую карту и проверяем радио детали если горит зеленым цветом то радио деталь рабочая если горит желтым то радио деталь полу рабочая тоест луче поменять если горит красным то радио деталь не рабочая.Нужна помочт раработки?

   Ответить

   1. 1. это будет очень непростая по коду и размеру программа
      2. просто со входа звуковой карты (микрофонный?) так проверить не получится – это вход АЦП, на него можно подавать напряжение, но без внешнего источника напряжения подключать туда “радиодеталь” бессмысленно…
      3. даже решив вопрос с источником напряжения, так проверять параметры вы сможете очень немногих простейших радиодеталей: диода, некоторых резисторов … транзистор вы уже не проверите, не говоря уже о более сложных устройствах.
      4. такая программа (даже если бы вы её при всех ограничениях возможностей сделали) будет зависимой от операционной системы: работающая под Windows не будет работать под Linux, если вы сделаете под Linux – она не будет работать под FreeBSD, сделаете под FreeBSD – не будет работать под Solaris и т.д.

      В сети есть довольно много программ компьютерных осциллографов, подключаемых ко входу аудиокарты. Многие из них – с открытым кодом. Возьмите код таких программ и смотрите как они работают с аудиовходом.

      Ответить

5. 
#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;
}


   Ответить

6. Я начинающий программист С++ и возможно код будет громоздкий, но как получилось.

   
#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;
}


   Ответить

7. Здравствуйте. Помогите, пожалуйста. Распишите как работает каждая строка в решении (первый вариант).

   Ответить

8. Осилил c#:

   using System;

   namespace Homework5
   {
   class Program
   {
   static bool check(string text)
   {
   int count = 0;
   char[] memory = new char[100];
   foreach (char element in text)
   {
   switch (element)
   {
   case ‘{‘: memory[++count] = element; break;
   case ‘(‘: memory[++count] = element; break;
   case ‘[‘: memory[++count] = element; break;
   case ‘}’: if (memory[count] == ‘{‘) { count–; } else { return false; }; break;
   case ‘)’: if (memory[count] == ‘(‘) { count–; } else { return false; }; break;
   case ‘]’: if (memory[count] == ‘[‘) { count–; } else { return false; }; break;
   }
   }
   return count == 0 ? true : false;
   }
   static void Main(string[] args)
   {
   Console.WriteLine(check(Console.ReadLine()));
   Console.ReadKey(true);
   }
   }
   }

   Ответить