Переход от infix to postfix

Question

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

#define MAX_EQU_LEN 100 

static int prec(char operator) 
{ 
    switch (operator) 
    { 
     case '*': 
      return 5; 
     case '/': 
      return 4; 
     case '%': 
      return 3; 
     case '+': 
      return 2; 
     case '-': 
      return 1; 
     default: 
      break; 
    } 

    return 0; 
} 

static int isNumeric(char* num) 
{ 
    if(atoi(num) == 0) 
    { 
     return 0; 
    } 
      return 1; 
} 

char* infix_to_postfix(char* infix) 
{ 
    char* postfix = malloc(MAX_EQU_LEN); 
    stack* s = create_stack(); 
    s->size = strlen(infix); 
    node* tempPtr = s->stack; 
    unsigned int i; 
    char symbol,next; 

    for(i = 0; i < s->size ; i++) 
    { 
     symbol = *((infix + i)); 
     tempPtr = s->stack; 
     if(isNumeric(&symbol) != 1) 
     { 
      strcat(postfix, &symbol); 
     } 
     else if(symbol == '(') 
     { 
      push(s, symbol); 
     } 
     else if(symbol == ')') 
     { 
      while(s->size != 0 && top(s) != '(') 
      { 
       next = tempPtr->data; 
       pop(s); 
       strcat(postfix, &next); 
       tempPtr = s->stack; 
       if(tempPtr->data == '(') 
       { 
        pop(s); 
       } 
      } 
     } 
     else 
     { 
      while(s->size != 0 && prec(top(s)) > prec(symbol)) 
      { 
       next = tempPtr->data; 
       pop(s); 
       strcat(postfix, &next); 
       push(s,next); 
      } 
     } 
     while(s->size != 0) 
     { 
      next = tempPtr->data; 
      pop(s); 
      strcat(postfix, &next); 
     } 
    } 
    return postfix; 

} 

int evaluate_postfix(char* postfix) { 

    //For each token in the string 
     int i,result; 
     int right, left; 
     char ch; 
     stack* s = create_stack(); 
     node* tempPtr = s->stack; 

     for(i=0;postfix[i] < strlen(postfix); i++){ 
      //if the token is numeric 
      ch = postfix[i]; 
      if(isNumeric(&ch)){ 
       //convert it to an integer and push it onto the stack 
       atoi(&ch); 
       push(s, ch); 
      } 
      else 
      { 
       pop(&s[i]); 
       pop(&s[i+1]); 
       //apply the operation: 
       //result = left op right 
         switch(ch) 
         { 
          case '+': push(&s[i],right + left); 
            break; 
          case '-': push(&s[i],right - left); 
            break; 
          case '*': push(&s[i],right * left); 
            break; 
          case '/': push(&s[i],right/left); 
            break; 
         } 
       } 
     } 
     tempPtr = s->stack; 
     //return the result from the stack 
     return(tempPtr->data); 

} 

Этот файл является частью программы, которая использует стек структуры для выполнения инфикса postfix во входном файле. Другие функции были протестированы и работают нормально, но когда я пытаюсь добавить эту часть и фактически выполняю операции, сегментирование программных ошибок. Отладчик говорит, что это происходит в функции infix_to_postfix, однако он не говорит, какую строку и я не могу понять, где. Кто-нибудь знает, почему это произойдет?

Answer 1

Вы сделали несколько вещей неправильно:

if(isNumeric(&symbol) != 1) 

Функция isNumeric() ожидает нулевую строку завершающейся в качестве входных данных, а не указатель на один символ.

 strcat(postfix, &symbol); 

Здесь же самое относится.

 strcat(postfix, &next); 

Я предполагаю, что это тоже неправильно. Если вы хотите превратить один символ в строку, вы можете сделать это:

char temp[2] = {0}; 

temp[0] = symbol; 
strcat(postfix, temp); 

Answer 2

static int isNumeric(char* num) 
{ 
    if(atoi(num) == 0) 
    { 
     return 0; 
    } 
      return 1; 
} 

Что делать, если строка "0"? Подумайте, вместо этого используйте strtol, потому что он предлагает более мощные средства для проверки успеха результата.

Несвязанное стилистическое примечание: ваша первая функция выглядит сложнейшей для меня. Хотя вполне возможно, что так, как я это делаю, тоже слишком сложно.

static int prec(char operator) 
{ 
    switch (operator) 
    { 
     case '*': 
      return 5; 
     case '/': 
      return 4; 
     case '%': 
      return 3; 
     case '+': 
      return 2; 
     case '-': 
      return 1; 
     default: 
      break; 
    } 

    return 0; 
} 

Если функция выполняет простое отображение из одного набора к другому, как правило, Это может быть выполнено более просто (и быстрее) в качестве поиска массива. Поэтому я бы начал с строки ввода символов.

char *operators = "*" "/" "%" "+" "-"; 

Обратите внимание, что компилятор свяжет их с одним строковым значением с нулевым терминатором.

int precedence[] = { 5, 4, 3, 2, 1, 0 }; 

Затем тестирование является ли символ является оператором:

#include <string.h> 
if (strchr(operators, chr)) 
    ...; 

И получая преимущество становится:

p = precedence[strchr(operators, chr) - operators]; 

Если есть несколько значений ассоциируют с оператором, я d рассмотреть возможность использования X-Macro для генерации таблицы и набора связанных значений enum для использования в качестве символических индексов.