Рекурсивная реализация стека без массивов POP не работает - PullRequest
Новая
       15

Рекурсивная реализация стека без массивов POP не работает

0 голосов
/ 09 июня 2019

Я пытаюсь рекурсивно реализовать стек LIFO без использования массивов.Программа принимает в качестве входных данных строки и целые числа и имеет несколько команд, а именно: push <int> pop empty top и quit.

Все, кроме pop у меня работает нормально, а pop работает только частично.Это нормально, если вы получаете только один int, но кроме этого он возвращает мне stack is empty, хотя это не так.Я понимаю, почему это происходит, но я не уверен, как это исправить.

int stack(int top, int last) {  
  int m = read_symbol();
  if (m != READ_FAIL) {
    if (m == PUSH_SYMBOL) {
      int n = read_int();
      top = stack(n, top);
    } else if (m == POP_SYMBOL) {
      if (top == INT_MIN) {
        printf("pop error - stack is empty\n");
        top = stack(INT_MIN, INT_MIN);
      } else {
        top = stack(last, INT_MIN);
      }
    } else if (m == TOP_SYMBOL) {
      if (top == INT_MIN) {
        printf("top error - stack is empty\n");
      } else {
        printf("top - %d\n", top);
      }
      top = stack(top, last);
    } else if (m == EMPTY_SYMBOL) {
      if (top == INT_MIN) {
        printf("stack is empty\n");
      } else {
        printf("stack is not empty\n");
      }
      top = stack(top, last);
    } else if (m == QUIT_SYMBOL) {
      if (top != INT_MIN) {
        printf("quit error - stack is not empty\n");
        top = stack(top, last);
      } else {
        printf("goodbye\n");
      }
    }
  }
  return top;
}

Переменная top возвращается рекурсивно, поэтому все работает нормально.Но когда я делаю что-то вроде 

push 1
push 2
push 3
top
pop
top
pop
top

, возвращается результат 

top - 3
top - 2
top error - stack is empty (SHOULD BE 1)

, я пробовал разные подходы, но я не смог решить его.Фактически я ввел параметр last просто для того, чтобы попытаться решить эту проблему, остальная часть реализации работает нормально даже без last, но пока этот параметр работает, но только для одной команды pop, потому что устанавливается следующий уровень рекурсииlast до INT_MIN, который затем устанавливается на top, если вы снова pop, следовательно, ложное stack is empty сообщение

любые указатели или помощь будут оценены.

РЕДАКТИРОВАТЬ: INT_MIN относится к C99 limits.h INT_MIN, что составляет - (2 ^ 32 - 1)

Ответы [ 2 ]

0 голосов
/ 09 июня 2019

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

int stack(int top, int last) {
  switch(read_symbol()) {

    // push n
    case PUSH_SYMBOL:  
      return stack(read_int(), top);

    // pop
    case POP_SYMBOL:
      if (top == INT_MIN) {
        printf("pop error - stack is empty\n");
        return stack(INT_MIN, INT_MIN);
      }

      return stack(last, INT_MIN);

    // top  
    case TOP_SYMBOL:
      if (top == INT_MIN)
        printf("top error - stack is empty\n");
      else
        printf("top - %d\n", top);

      return stack(top, last);

    // empty
    case EMPTY_SYMBOL: 
      if (top == INT_MIN)
        printf("stack is empty\n");
      else
        printf("stack is not empty\n");

      return stack(top, last);

    // quit
    case QUIT_SYMBOL:
      if (top != INT_MIN) {
        printf("quit error - stack is not empty\n");
        return stack(top, last);
      }

      printf("goodbye\n");

    case READ_FAIL: // error handling
    default:
      return top;
  }
}

Затем я следовал за предполагаемым стеком вызовов: 

stack(INT_MIN, INT_MIN) receives PUSH 1 -> stack(1, INT_MIN)
stack(1, INT_MIN)       receives PUSH 2 -> stack(1, 2)
stack(1, 2)             receives PUSH 3 -> stack(3, 2)
stack(3, 2)             receives TOP    -> stack(3, 2)
stack(3, 2)             receives POP    -> stack(2, INT_MIN)
stack(2, INT_MIN)       receives TOP    -> stack(2, INT_MIN)
stack(2, INT_MIN)       receives POP    -> stack(INT_MIN, INT_MIN)
stack(INT_MIN, INT_MIN) receives TOP    => ERROR

Проблема здесь очень проста, стек вызовов pop (x, INT_MIN), который в вашем коде означает, что после pop стек имеет только размер1 (или ноль).Данные из предыдущего стека вызовов не используются.

0 голосов
/ 09 июня 2019

внутри, если (m == POP_SYMBOL) {} изменить 

if (top == INT_MIN)

до 

if (top < INT_MIN)

и дайте мне знать, если это работает для вас, как это может произойти из-за неправильной логики для переменной 'top' для, например. мы можем думать в нашей логике, что переменная «top» нарушена, тогда как на самом деле она будет нарушена для следующей итерации. Если это не сработает, то отправьте значение INT_MIN (возможно, это значение # define-ed)

...