Булева функция для рекурсивной проверки правильности выражения? - PullRequest
Новая
       23

Булева функция для рекурсивной проверки правильности выражения?

0 голосов
/ 13 февраля 2012

Я хочу создать вид парсера вида: 

#include <iostream>
#include <string>
#include <sstream>
#include <cctype>

using namespace std;

bool isValid(istringstream& is)
{
  char ch;
  is.get(ch); //I know get(ch) is a good start but this is as for as I got :)
  .......
  ....
}

int main()
{
  string s;
  while(getline(cin,s))
  {
    istringstream is(s);
    cout<<(isValid(is)? "Expression OK" : "Not OK")<<endl;
  }
}

Булева функция, которая возвращает TRUE, если последовательность char имеет форму "5" или "(5 + 3)" или "((5 + 3) +6)" или "( ((4 + 2) +1) +6) "... и т. Д. И FALSE для любого другого случая

По сути, выражение будет считаться действительным, если оно будет либо одной цифрой, либо в форме "открытая скобка-одна цифра плюс знак-одна цифра-закрывающая скобка"

  • Действительное выражение = одна цифра

    и

  • Действительное выражение = ( Действительное выражение + Действительное выражение )

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

Будучи новичком, которым я являюсь .. Спасибо за любой полезный вклад!

1 Ответ

0 голосов
/ 13 февраля 2012

Чтобы сделать рекурсивное решение, вам нужно сначала прочитать строку в буфер, а затем сделать что-то вроде этого: 

int expression(char* str) {
    if (*str == '(') {
        int e1 = expression(str + 1);
        if (e1 == -1 || *(str + 1 + e) != '+') {
            return -1;
        }
        int e2 = expression(str + 1 + e + 1);
        if (e2 == -1 || *(str + 1 + e + 1 + e2) != ')') {
            return -1;
        }
        return 1 + e1 + 1 + e2 + 1;
    }

    if (*str >= '0' || *str <= '9') {
        return 1;
    }

    return -1;
}

bool isvalid(char* str) {
    int e1 = expression(str);
    if (e1 < 0) {
        return false;
    }
    if (e1 == strlen(str)) {
        return true;
    }
    if (*(str + e1) != '+') {
        return false;
    }
    int e2 = expression(str + e1 + 1);
    if (e2 < 0) {
        return false;
    }
    return (e1 + 1 + e2 == strlen(str));
}

По сути, функция выражения возвращает длину действительного выражения вэто аргумент.Если его аргумент начинается с круглой скобки, он получает длину выражения после этого, проверяет плюс после этого, а затем проверяет закрывающую скобку после следующего выражения.Если аргумент начинается с числа, верните 1. Если что-то напутало, верните -1.Затем, используя эту функцию, мы можем выяснить, является ли строка допустимой по некоторым суммам и по длине строки.

Я вообще не тестировал функцию, но единственный случай, когда это может не сработать, -Я могу подумать, будет ли чрезмерная скобка: ((5)), например.

Альтернативой рекурсии может быть какой-то лексический синтаксический анализ, такой как: 

enum {
    ExpectingLeftExpression,
    ExpectingRightExpression,
    ExpectingPlus,
    ExpectingEnd,
} ParseState;

// returns true if str is valid
bool check(char* str) {
    ParseState state = ExpectingLeftExpression;

    do {
        switch (state) {
            case ExpectingLeftExpression:
                if (*str == '(') {
                } else if (*str >= '0' && *str <= '9') {
                    state = ExpectingPlus;
                } else {
                    printf("Error: Expected left hand expression.");
                    return false;
                }
            break;
            case ExpectingPlus:
                if (*str == '+') {
                    state = ExpectingRightExpression;
                } else {
                    printf("Error: Expected plus.");
                    return false;
                }
            break;
            case ExpectingRightExpression:
                if (*str == '(') {
                    state = ExpectingLeftExpression;
                } else if (*str >= '0' && *str <= '9') {
                    state = ExpectingEnd;
                } else {
                    printf("Error: Expected right hand expression.");
                    return false;
                }
            break;
        }
    } while (*(++str));

    return true;
}

Эта функция незавершить на всех, но вы должны быть в состоянии увидеть, куда он идет.Я думаю, что рекурсия в этом случае работает лучше в любом случае.

...