Сохранение префикса Выражение (рекурсивное)

Question

Спасибо за чтение. Мне действительно нужна помощь здесь. Я столкнулся с проблемой, которая включает в себя использование рекурсивного метода для хранения полностью помеченного пользователем префиксного выражения. В этом конкретном случае числа идентифицируются символом «n», тогда как символы и т. Д. Такие же, как и они. Так, например, это:

% 18 + 14/(12 - 11) - 1183% 17

бы быть введены в командной строке, так как это:

• % N18/N14 - n12 n11% n1183 n17

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

Expr * readFPInfix(std::istream & infile) 
{ 
    static std::string ops("*+/%-"); 
    char symbol; 
    infile >> symbol; 
    if (symbol == 'n') 
    { 
     long number; 
     infile >> number; 
     return new Atom(number); 
    } 
    else if (symbol == '(') 
    { 
     Expr * left = readFPInfix(infile); 
     char op; 
     infile >> op; 
     if (ops.find(op) == std::string::npos) { 
      std::cout << "Unknown operator symbol '" << op << "'" << std::endl; 
      system("pause"); 
      exit(0); 
     } 
     Expr * right = readFPInfix(infile); 
     infile >> symbol; 
     // read the ending right parenthesis 
     if (symbol != ')') { 
      std::cout << "Invalid symbol '" << symbol << "': ')' expected" << std::endl; 
      system("pause"); 
      exit(0); 
     } 
     switch (op) 
     { 
     case '*': 
      return new Times(left, right); 
     case '+': 
      return new Plus(left, right); 
     case '/': 
      return new Divide(left, right); 
     case '%': 
      return new Mod(left, right); 
     case '-': 
      return new Subtract(left, right); 
     default: 
      std::cout << "Read error" << std::endl; 
      system("pause"); 
      exit(0); 
     } 
    } 
    else 
    { 
     std::cout << "Invalid symbol '" << symbol << "': 'n' or '(' expected" << std::endl; 
     system("pause"); 
     exit(0); 
    } 
} 

Теперь, я предполагаю, что мы должны использовать один и тот же материал, так что моя основная проблема заключается в чтении проклятого выражения. Я понимаю, что в этом методе мы читаем его символом по символу, а затем тестируем этот символ против подсказок, чтобы проверить, является ли он оператором или номером. Хорошо, круто. Но как мне получить левый и правый, поэтому я могу ввести его в нечто вроде Плюс (слева, справа). Я действительно борется, поэтому любая помощь будет очень оценена.

ПРИМЕЧАНИЕ. Это задание домашней работы, поэтому, если кто-то дает мне ответ, это хорошо, или псевдокод тоже прекрасен. Спасибо.

Answer 1

Теперь ... как я уже говорил выше, это не место, где мы просто передаем вам дизайн или кодирование. Однако, я думаю, я все еще в пределах, чтобы объяснить, как infix разбивается на левый и правый операнды.

Существует только два типа операндов в инфикс: терминал (постоянный или переменный) и выражение.

Каждое выражение имеет ту же форму:

operator left-operand right-operand 

Как оказалось, можно легко разобрать сложное выражение, используя эти два правила: каждый раз, когда вы нажмете оператора, вы начинаете новое выражение (т.е. сделать рекурсивный вызов). Перейдем к юридической версии вашего примера:

% 18 + 14/- 12 11 % 1183 17 

Первое, что мы находим, это%; сохраните оператора и ищите левый и правый операнды в оставшейся строке, 18 + 14/- 12 11 % 1183 17. Левое тривиально; там есть постоянная.

// expression 1 
operator = '%' 
left = '18' 
right = '+ 14/- 12 11 % 1183 17' 

Это дает нам полное выражение верхнего уровня. Однако нам еще нужно проанализировать правый операнд. Это еще одно выражение. Зафиксируйте + как оператор и проанализируйте два операнда.

Опять же, левое тривиально; правой остается остальная часть выражения:

// expression 2 
operator = '+' 
left = '14' 
right = '/ - 12 11 % 1183 17' 

Опять же, нам еще нужно проанализировать правый операнд.Пристань / как оператор, и ... ха! На этот раз левый операнд является выражением. Мы все еще передаем всю строку в парсер выражений.

// expression 3 
operator = '/' 
left = <something from> '- 12 11 % 1183 17' 
right = <on hold> 

Вот шаги, которые я пропустил до сих пор. Когда мы делаем рекурсивный вызов, мы передаем все выражение. Оценка левого операнда будет потреблять все, что ему нужно, оставив остальную часть для правильной оценки. Давайте рассмотрим это немного более тщательно сейчас ...

// выражение 4 оператор = '-' слева = 12 право = 11 Остаточные = '% 1183 17'

Этот остаток должен передаваться обратно вызывающему экземпляру для использования для правильного оператора. Найдя левый операнд (и оценивает его в 1), мы вернемся к нашему разборе выражения 3:

// expression 3 
operator = '/' 
left = 1 
right = '% 1183 17' 

Теперь мы также разобрать правую строку, получив значение 1183% 17 или 10. Примечания что я не хожу через это выражение 5; как выражение 4, это простая операция, ['%', 1183, 17].

Наконец, мы возвращаемся к выражению 3 и делаем 1/10 (целочисленная арифметика дает нам 0 для этого). То, что 0 становится правой частью для выражения 2, где мы оцениваем 14 + 0. Наконец, этот результат становится правой частью выражения 1, а окончательный ответ равен 18% 14 или 4.

Теперь ... может вы программируете оттуда?