1

Нужно построить синтаксический анализатор для понятия скобки. Программа на все выдает неправильные ответы, хотя написана, как мне кажется, верно. Помогите, пожалуйста, найти ошибку.

скобки::=квадратные | круглые квадратные:: = [ [ квадратные ] ( круглые ) ] | B круглые::=( ( круглые ) [ квадратные ] ) | А

#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
using namespace std;

bool Brackets ( istream &is );

bool Square ( istream &is );

bool Round ( istream &is );

int main()

{
  string str;

  cout << "Welcome to program Syntax Analysis of Bracket!" << endl;

  cout << "Input your string: " << endl;

  getline(cin, str);
  istringstream is(str);

  Brackets(is);

  if ((!Brackets(is)) || (is.peek() >= 0))
        cout << "This isn't a brackets" << endl; //Brackets = false

  if (Brackets(is))
      cout << "This is a brackets" << endl;

  system ("pause");
  return 0;     
}

bool Brackets( istream &is )
{
    if (Round(is) || Square(is))
        return true;
    else
        return false;
}

bool Round( istream &is )
{

          if (is.peek() == 'A')
          {
                is.get();
                return true;

          }

        if (is.peek() != '(')  
            return false;
        is.get();
        if (is.peek() != '(') 
            return false;
        is.get();
        if (!Round( is ))     
            return false;
        if (is.peek() != ')')  
            return false;
        is.get();
        if (is.peek() != '[') 
            return false;
        is.get();
        if (!Square( is ))    
            return false;
        if (is.peek() != ']')  
            return false;
        is.get();
        if (is.peek() != ')') 
            return false;
        is.get();

}

bool Square( istream &is )
{

             if (is.peek() == 'B')
             {
                is.get();
                return true;

             }

                if (is.peek() != '[')
                    return false;
                is.get();
                if (is.get()!= '[')  
                    return false;
                is.get();
                if (!Square( is ))   
                    return false;
                if (is.peek() != ']') 
                    return false;
                is.get();
                if (is.peek() != '(') 
                    return false;
                is.get();
                if (!Round( is ))    
                    return false;
                if (is.peek() != ')') 
                    return false;
                is.get();
                if (is.peek() != ']') 
                    return false;
                is.get();

}
1
  • Вы не поняли запись. Запись условия задачи говорит нам, что скобки бывают или квадратные, или круглые. Внутри скобок могут быть вложенные скобки одного типа или другого. Уровень вложенности - любой. Также внутри может встречаться любой набор символов. Вариантов тут разбора два. Или использовать внешнюю структуру данных, или сделать ф-ции для действий при получении во входной строке определенных символов.
    – gecube
    18 окт 2011 в 21:05

2 ответа 2

3

Классически данная задача решается с помощью стека. Мы идем по последовательности скобок (например, просто пропуская другие символы в строке), если нам встречается открывающая скобка любого типа, то она помещается в стек.

В случае, если встречается закрывающая скобка, то со стека снимается верхняя скобка. В случае, если типы не совпадают, то в скобочной структуре ошибка. Также в ней ошибки, если мы пытаемся снять со стека скобку, а стек пуст или в том случае, если мы дошли до конца строки, а в стеке еще что-то есть.


Как говорится, we won't insult your intelligence, и данный код вы можете написать самостоятельно, воспользовавшись, например, адаптером STL std::stack или любым стандартным контейнером типа std::vector.

1
  • 1
    Кстати говоря, такое использование is.peek() - это очень сурово, и в продакшене за такое бьют по рукам :) 18 окт 2011 в 21:03
0

я когда-то решал таким способом:

#include<iostream>
using namespace std;
int main(){
int square;
int round;
char ch;
while(cin.get(ch)){
if (ch=='(')
round++;
if (ch==')')
round--;
if (ch=='[')square++;
if (ch==']')square--;
}
if (!square && !round)cout << "Выражение правильное\n";
2
  • Это неправильно. У Вас любая мешанина где количество открывающих и закрывающих круглых и количество открывающих и закрывающих квадратных равны будет признана правильной. Например: (]))[(
    – avp
    24 окт 2011 в 10:39
  • По ходу даже не поможет добавка условия, что round и square ни в какой момент времени не станут отрицательными.
    – gecube
    21 окт 2012 в 2:30

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.