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

Question

Я хочу создать своего рода парсер формы:

#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, если последовательность полукокса имеет вид «5» или «(5 + 3)» или "((5 + 3) +6)" или "((4 + 2) +1) +6)" ... и т. Д. И FALSE для любого другого случая

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

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

  и

• допустимое выражение = (допустимое выражение + допустимое выражение)

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

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

Answer 1

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

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

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