4

私は C で、整数と"+ - * /"演算子だけを含む Lisp 算術計算機の単純なプログラムを作成しています。これは、宿題などではなく、学習目的で行っています。

したがって、このようなものを正しく解析して(+ 2 3)5を出力する関数を作成したので、ネストされていないステートメントを処理する方法は知っていますが、この(+ (* 2 3) (- 4 2))ようなものがある場合はどうすればよいので、再帰を使用してこれを解決できるようですが、私はしませんそれを行う方法を本当に知りません。

私のロジックは次のとおりです（疑似コードで）：`

  function parse_line(int n)
    get_input(string);
    if string[n] == '('
     if string[n+1] == operator
      if string[n+3] == number
       result = parseAllNumbers(); //between ( )
       return result; 
    if string[n+3] == '('
     parse_line(n+2);

`

ここで私の論理は正しいですか。もしあれば、計算(+ (* 2 3) (- 4 2))するだけです。を計算してから、これら 2 つの結果を加算する(* 2 3)にはどうすればよいでしょうか。(- 4 2)

4

3 に答える 3

5

あなたは間違いなく正しい方向に進んでいます。

getToken()文字列内の次の論理トークンを現在の位置から読み取る関数が記述されていると仮定します。論理トークンは、数値'（'、'）'または4つの演算子のいずれかです。次に、式を再帰的に評価できます。

function evaluateExpression(){
    var token = getToken();

    if( isNumber(token)){
        return token;
    }else if( isOpenParen(token)){
        return evaluateExpression();
    }

    var numOne = evaluateExpression();
    var nextToken = null;
    while( !isRightParen(nextToken)){
        nextToken = getToken();
        numOne = evaluate(token, numOne, nextToken);
    }

    return numOne;
}

関数isNumber()とisLeftParen()それらが意味することを実行し、渡されたトークンがそれぞれ数値または左括弧の場合はtrueを返します。このevaluate()関数は、演算子トークンと2つの数値を取得してそれらを評価します。たとえば、evaluate(+,2,4)戻り6、evaluate(-,2,4)戻り2ます。

于 2012-08-14T21:38:14.860 に答える
2

再帰を使用するソリューションは次のとおりです。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define OPERATOR 0
#define OPEN_PAREN 1
#define CLOSE_PAREN 2
#define NUMBER 3
#define END_OF_EXPR 4

#define BAD_LINE 1
#define GOOD_LINE 0




typedef struct 
{
   unsigned char type;
   char operator;
   int number;
} token;

token tokens[100];
int num_tokens = 0;
int token_counter = 0;

token get_token(void)
{

   token temp;
   if ( token_counter < num_tokens )
   {
      temp = tokens[token_counter];
      token_counter += 1;
   }
   else
   {
      temp.type = END_OF_EXPR;
   }
   return temp;
}


int tokenize(const char *line, token *tokens,int *num_tokens)
{
   token_counter = 0;
   int number_digit = 0;
   token aToken;
   int length = strlen(line);
   char number_array[20];
   *num_tokens = 0;
   int num_open_paren = 0;
   int num_close_paren = 0;
   for (int i = 0; i < length; i++)
   {
      /* ignore whitespace */
      if ( line[i] == ' ' || line[i] == '\t' || line[i] == '\n' || line[i] == '\r' )
      {
         if ( number_digit > 0 )
         {
            number_array[number_digit] = '\0';
            aToken.number = atoi(number_array);
            aToken.type = NUMBER;
            tokens[*num_tokens] = aToken;
            *num_tokens += 1;       
            number_digit = 0;   
         }
      }
      else if ( line[i] == '(')
      {
         aToken.type = OPEN_PAREN;
         tokens[*num_tokens] = aToken;
         *num_tokens += 1;
         num_open_paren += 1;
      }
      else if (line[i] == ')' )
      {
         if ( number_digit > 0 )
         {
            number_array[number_digit] = '\0';
            aToken.number = atoi(number_array);
            aToken.type = NUMBER;
            tokens[*num_tokens] = aToken;
            *num_tokens += 1;           
            number_digit = 0;
         }
         aToken.type = CLOSE_PAREN;
         tokens[*num_tokens] = aToken;
         *num_tokens += 1;
         num_close_paren += 1;
      }
      else if ( line[i] == '*' || line[i] == '+' ||  
           line[i] == '/' || line[i] == '-' )
      {
         aToken.type = OPERATOR;
         aToken.operator = line[i];
         tokens[*num_tokens] = aToken;
         *num_tokens += 1;       
      }
      else if ( isdigit(line[i]) )
      {
         number_array[number_digit] = line[i];
         number_digit += 1;
      }
      else
      {
         printf("%c - the %d character - is illegal\n",line[i],i+1);
         return BAD_LINE;
      }

   }
   if ( num_open_paren == num_close_paren )
   {
      return GOOD_LINE;
   }
   else
   {
      printf("mismatched parentheses\n:%s\n",line);
      return BAD_LINE;
   }
}


int evaluate(char operator, int *operands, int num_operands)
{
   int result = 0;
   switch (operator)
   {    
      case '+':
         for (int i = 0; i < num_operands; i++)
         {
            result += operands[i];
         }
         break;
      case '-':
         result = operands[0];
         for (int i = 1; i < num_operands; i++)
         {
            result -= operands[i];
         }
         break;
      case '*':
         result = operands[0];
         for (int i = 1; i < num_operands; i++)
         {
            result *= operands[i];
         }    
         break;
      case '/':
         result = operands[0];
         for (int i = 1; i < num_operands; i++)
         {
            result /= operands[i];
         }    
         break;   
      default:
         printf("ERROR invalid operator: %c\n",operator);
   }
   return result;
}

int process_expression(void)
{
   int result = 0;
   token current_token = get_token();
   if ( current_token.type != OPERATOR )
   {
      fprintf(stderr,"ERROR: %s expecting operator\n",__func__);
      exit(1);
   }
   char operator = current_token.operator;
   current_token = get_token();
   int operands[200];
   int operands_index = 0;
   while ( current_token.type != CLOSE_PAREN && current_token.type != END_OF_EXPR)
   {
      if ( current_token.type == NUMBER )
      {
         operands[operands_index] = current_token.number;
         operands_index += 1;
      }
      else if ( current_token.type == OPEN_PAREN )
      {
         operands[operands_index] = process_expression();
         operands_index += 1;
      }
      current_token = get_token();
   }
   result = evaluate(operator,operands,operands_index);
   return result;
}

void process_lisp_string(const char *line)
{

   int result = tokenize(line, tokens,&num_tokens);

   if ( result == GOOD_LINE )
   {
      token first = get_token();
      if ( first.type == OPEN_PAREN )
         printf("the answer for %s is: %d\n",line, process_expression());
      else
      {
         fprintf(stderr,"ERROR: no open parentheses at front of expression\n");
         fprintf(stderr,"token type:%d\n",first.type);
      }
   }
   else 
   {
      printf("the line contained errors\n");
   }
}

int main(const int argc, const char *const argv[])
{
   char *test = "(+ 2 2 )";
   char *line = "(+ (+ 30 20) 2 2)";
   char *line2 = "(- (+ 1000 10) 200)";
   char *line3 = "(- (+ 1000 10) (- 200 10) (* 2 4))";
   char *line4 = "(+ (+ 10 10) (* 2 4) (* 2 3) (* 2 (- 3 1)))";
   process_lisp_string(test);
   process_lisp_string(line);
   process_lisp_string(line2);
   process_lisp_string(line3);
   process_lisp_string(line4);
}

出力：

the answer for (+ 2 2 ) is: 4
the answer for (+ (+ 30 20) 2 2) is: 54
the answer for (- (+ 1000 10) 200) is: 810
the answer for (- (+ 1000 10) (- 200 10) (* 2 4)) is: 812
the answer for (+ (+ 10 10) (* 2 4) (* 2 3) (* 2 (- 3 1))) is: 38
于 2012-08-15T19:37:18.417 に答える
1

Cは最も使いにくい言語です。これが宿題でない限り、最初に別の高水準言語で試すのがおそらく最善です。C には文字列がなく、スタックのようなデータ構造もありません。この処理は、他のポスターが示唆したように、おそらくよりエレガントに再帰的に行われますが、非再帰の方が簡単だと思います。以下は、正の整数のみを処理し、一部のエラー処理を欠いている部分的なソリューションです。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#define OPERATOR 0
#define OPEN_PAREN 1
#define CLOSE_PAREN 2
#define NUMBER 3

#define BAD_LINE 1
#define GOOD_LINE 0

typedef struct 
{
   unsigned char type;
   char operator;
   int number;
} token;




int get_tokens(const char *line, token *tokens,int *num_tokens)
{
   int number_digit = 0;
   token aToken;
   int length = strlen(line);
   char number_array[20];
   *num_tokens = 0;
   int num_open_paren = 0;
   int num_close_paren = 0;
   for (int i = 0; i < length; i++)
   {
      /* ignore whitespace */
      if ( line[i] == ' ' || line[i] == '\t' || line[i] == '\n' || line[i] == '\r' )
      {
         if ( number_digit > 0 )
         {
            number_array[number_digit] = '\0';
            aToken.number = atoi(number_array);
            aToken.type = NUMBER;
            tokens[*num_tokens] = aToken;
            *num_tokens += 1;       
            number_digit = 0;   
         }
      }
      else if ( line[i] == '(')
      {
         aToken.type = OPEN_PAREN;
         tokens[*num_tokens] = aToken;
         *num_tokens += 1;
         num_open_paren += 1;
      }
      else if (line[i] == ')' )
      {
         if ( number_digit > 0 )
         {
            number_array[number_digit] = '\0';
            aToken.number = atoi(number_array);
            aToken.type = NUMBER;
            tokens[*num_tokens] = aToken;
            *num_tokens += 1;           
            number_digit = 0;
         }
         aToken.type = CLOSE_PAREN;
         tokens[*num_tokens] = aToken;
         *num_tokens += 1;
         num_close_paren += 1;
      }
      else if ( line[i] == '*' || line[i] == '+' ||  
           line[i] == '/' || line[i] == '-' )
      {
         aToken.type = OPERATOR;
         aToken.operator = line[i];
         tokens[*num_tokens] = aToken;
         *num_tokens += 1;       
      }
      else if ( isdigit(line[i]) )
      {
         number_array[number_digit] = line[i];
         number_digit += 1;
      }
      else
      {
         printf("%c - the %d character - is illegal\n",line[i],i+1);
         return BAD_LINE;
      }

   }
   if ( num_open_paren == num_close_paren )
   {
      return GOOD_LINE;
   }
   else
   {
      printf("mismatched parentheses\n:%s\n",line);
      return BAD_LINE;
   }
}

int process_expression(char operator, int *operands, int num_operands)
{
   int result = 0;
   switch (operator)
   {    
      case '+':
         for (int i = 0; i < num_operands; i++)
         {
            result += operands[i];
         }
         break;
      case '-':
         result = operands[0];
         for (int i = 1; i < num_operands; i++)
         {
            result -= operands[i];
         }
         break;
      case '*':
         result = operands[0];
         for (int i = 1; i < num_operands; i++)
         {
            result *= operands[i];
         }    
         break;
      case '/':
         result = operands[0];
         for (int i = 1; i < num_operands; i++)
         {
            result /= operands[i];
         }    
         break;   
      default:
         printf("ERROR invalid operator: %c\n",operator);
   }
   return result;
}

int process_tokens(token *tokens, int num_tokens)
{
   int result = 0;
   /* operators "stack" */
   char operators[100];
   /* "pointer" for current operator */
   int operator_index = -1;
   /* operands "stack" 1 row for each operator (set of parentheses) */
   int operands[100][20];
   /* how many operands for current expression? (current operator) */
   int expression_operands[100];
   for (int i = 0; i < num_tokens; i++)
   {
      if ( tokens[i].type == OPEN_PAREN )
      {
         operator_index += 1;
         expression_operands[operator_index] = 0;
      }
      else if ( tokens[i].type == CLOSE_PAREN )
      {
         result = process_expression(operators[operator_index], 
                                          &operands[operator_index][0],
                                          expression_operands[operator_index]);
         operator_index -= 1;
         if ( operator_index > -1 )
         {
            operands[operator_index][ expression_operands[operator_index] ] = result;
            expression_operands[operator_index] += 1;
         }
      }
      else if ( tokens[i].type == OPERATOR )
      {
         operators[operator_index] = tokens[i].operator;
      }
      else if ( tokens[i].type == NUMBER )
      {
         operands[operator_index][ expression_operands[operator_index] ] = tokens[i].number;
         expression_operands[operator_index] += 1;
      }
   }
   return result;
}

void process_lisp_string(const char *string)
{
   token tokens[100];
   int num_tokens = 0;
   int result = get_tokens(string, tokens,&num_tokens);

   if ( result == GOOD_LINE )
   {
      printf("the answer is: %d\n",process_tokens(tokens,num_tokens));
   }
   else 
   {
      printf("the string contained errors\n");
   }
}

int main(const int argc, const char *const argv[])
{

   char *line = "(+ (+ 30 20) 2 2)";
   char *line2 = "(- (+ 1000 10) 200)";
   char *line3 = "(- (+ 1000 10) (- 200 10) (* 2 4))";
   char *line4 = "(+ (+ 10 10) (* 2 4) (* 2 3) (* 2 (- 3 1)))";
   process_lisp_string(line);
   process_lisp_string(line2);
   process_lisp_string(line3);
   process_lisp_string(line4);

}

結果：

the answer is: 54
the answer is: 810
the answer is: 812
the answer is: 38
于 2012-08-15T11:53:24.773 に答える