Оценка переменной из постфиксного выражения

Question

Я пытаюсь построить решатель для уравнений с одной переменной. Я использую алгоритм Shunting-yard, дополненный предложениями denver и rici . Очевидно, этот алгоритм отлично работает для анализа заданного математического выражения, определения его достоверности и оценки значения. Однако у меня возникли проблемы с пониманием того, как включить решение для определенной переменной.

Если я использую уравнение 2 * (x - 4) = 4, это можно без особой суеты преобразовать в RPN как 2 x 4 - * 4 -. Отсюда было бы легко оценить значение для любого данного x. Но как определить x? Я смотрю на gab's ответ, и хотя мне понятно, как построить дерево из формы RPN, я не понимаю, как рассчитать значение (шаг 5 в его ответе).

Спасибо.

Answer 1

Вы, что бы вы сделали, если бы решили это карандашом и бумагой: вы перемещаете вещи на другую сторону уравнения, пока не останется только x. Ваше дерево выглядит так:

        =
      /   \
    *       4
   / \
  2   −
     / \
    x   4

Все ветви - операторы, все листья - операнды. Путь от вашей единственной переменной прошел через узлы * и − в левой части. Это означает, что вы должны получить как можно больше материала с левой стороны на правую сторону, в идеале, пока не останется только узел x.

Первый узел слева является оператор умножения. Вы можете применить преобразование

a * b == c    ⟺    b = c / a

к дереву: уберите умножение слева и вставьте его обратную операцию, разделив на константу 2 справа. Ваше дерево теперь выглядит так:

        =
      /   \
    −       ÷
   / \     / \
  x   4   4   2

Деление действует на две константы. Вы можете «сложить» их в результат, 2:

        =
      /   \
    −       2
   / \ 
  x   4 

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

Теперь переместите оператор вычитания таким же образом:

        =
      /   \
    x       +
           / \
          2   4 

Рассчитать константное выражение справа, и вы получите x == 6.

Таким образом, вы в основном превращаете самый верхний левый оператор в его инверсию, пока не останется только переменная слева:

a + x == b   ⟺   x == b − a            x + a == b   ⟺   x == b − a
a − x == b   ⟺   x == a − b            x − a == b   ⟺   x == b + a
a * x == b   ⟺   x == b / a            x * a == b   ⟺   x == b / a
a / x == b   ⟺   x == a / b            x / a == b   ⟺   x == b * a

Если у вас есть только одна переменная и разрешены все константные выражения, ваш x будет переменной или операторным узлом; a будет постоянным числом.

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