문법 주어진 재귀

Question

문법이 주어진 재귀 프로그램을 구현할 것입니다. 나는 재귀의 개념을 이해하지만 그것을 구현하는 것은 압도적 일 수있다.

괄호가있는 문자열에 문제가 있습니다.

"(b-c)"를 입력하면 유효한 표현이되어야하지만 출력에 유효하지 않습니다.

나는 괄호를 다루는 프로그램을 추적 해 왔지만, 나는 틀린 곳을 알아내는 것처럼 보일 수있다.

또한 프로그램이 완벽하지 않을 수도 있지만이 문제를 해결하고 싶습니다. 어떤 도움을 주셔서 감사합니다.

입력하면 사용자에게 입력하라는 메시지가 나타납니다. 나는 필요한 것만 제공했다. 따라야 할

홈페이지

if(i.findExpression(str)){ 
    cout << str << " is legal infix expression.\n"; 
} 
else{ 
    cout << str << " is not a legal infix expression.\n"; 
} 

문법은 다음과 같습니다

표현 = 용어 | 용어 + 용어 | 용어 - 용어

term = factor | factor * factor | 인자/인자

인자 = 문자 | (식)

문자 = A | B | ... | Z

찾기 식

bool infix::findExpression(string strExp){ 
    int i; 
    int n = (int)strExp.length(); 
    bool found = true; 

    for (i = 0; i < n; i++){ 
     if((strExp.at(i) == '(') and (n != i)){ // 
      while((strExp.at(i)!=')') and (n != i)){ // 
       i++; 
      } 
      found = false; 
     } 
     else if((strExp.at(i) == '+' or strExp.at(i) == '-') and 
      (n != i)) 
     { 
      found = true; 
      break; 
     } 
     else 
      found = false; 
    }// added 
     if(found){ 
       return(findTerm(strExp.substr(0,i))&&findTerm(strExp.substr(i+1, n-(i+1)))); 
    } 
    else{ 
     return findTerm(strExp.substr(0,n)); 
    } 
} 

찾기 용어

bool infix::findTerm(string strExp){ 
    int n = (int)strExp.length(); 
    bool found = true; 
    int i; 

    for(i = 0; i < n; i++){ 
     if((strExp.at(i) == '(')and (n != i)){ 
      while((strExp.at(i)!=')')and (n != i)){ 
       i++; 
      } 
      found = false; 
     } 
     else if((strExp.at(i)=='*' or strExp.at(i)=='/')and (n != i)){ 
      found = true; 
      break; 
     } 
     else 
      found = false; 
    } 
    if(found){ 
     return(findFactor(strExp.substr(0,i)) &&  findFactor(strExp.substr(i+1, n-(i+1)))); 
    } 
    else{ 
     return findFactor(strExp.substr(0,n)); 
    } 
} 

찾기 인자

bool infix::findFactor(string strExp) 
    int i; 
    char ch; 
    int n = (int)strExp.length(); 
    bool found = true; 

    ch = strExp.at(0); 

    if((n==1)&&islower(ch)){ 
     return true; 
    } 
    else if(ch == '('){ 
     for(i = n; i > 0; i--){ 

      if((n-1 != i) and (strExp.at(i-1) == ')')){ 
       found = true; 
       break; 

      } 
      else{ 
       found = false; 

      } 

     } 
      if(found){ 
       return findExpression(strExp.substr(1, i-1)); 

      } 
      else{return false;} 

     } 
     else{return false;} 
} 

Answer 1

재귀 적 파서에는 일반적으로 규칙을 정확하게 반영하는 메서드가 있습니다. 규칙은 해당 입력을 사용합니다. 일반적으로 이것은 일종의 상태 저장 토큰 스트림을 조작하여 수행됩니다.

간단한 문자열을 사용하려는 경우 재귀 호출에 의해 소비되는 양을 처리하는 한 가지 방법은 재귀 호출이 새 위치를 반환하도록하는 것입니다. (일반적으로 토큰 스트림에서 작업하는 것이 좋습니다. 리턴 값을 사용하여 해당 서브 트리를 리턴합니다).

는이 경우, 예를 들어, 처리 표현하는 방법은 다음과 유사합니다 :

// expression = term | term + term | term - term 
// Returns the position in strExp after parsing, or -1 for errors. 
int infix::parseExpression(string strExp) { 
    int pos = parseTerm(strExp); 
    if (pos == -1) { // Error signal 
    return -1; 
    } 
    if (pos >= strExp.length()) { 
    return pos; // done 
    } 
    if (strExp.at(pos) != '-' && strExp.at(pos) != '+') { 
    return -1; // error 
    } 
    return parseTerm(strExpr.substr(pos + 1)); 
} 

// term = factor | factor * factor | factor/factor 
int infix::parseTerm(string strExp) { 
    ... 

표현식이 유효한지 여부를 제공해야 문자열 길이에 결과를 비교. 편의를 위해 다른 방법으로이 체크를 캡슐화 할 수 있습니다.