Проблема преобразования выражения

Question

Допустим, у нас есть следующее утверждение: s = 3 * a * b - 2 * c, где s, a, b и c - переменные.Кроме того, мы использовали алгоритм Shunting Yard для построения выражения RPN , поэтому теперь мы можем присвоить значения переменным a, b и c и вычислить значение sиспользуя простой анализатор RPN.

Но проблема в том, что я должен быть в состоянии вычислить значение любой переменной a, b или c, когда установлены значения всех других переменных.

Итак, мне нужно каким-то образом преобразовать существующее выражение, чтобы получить набор выражений:

a = (s + 2 * c) / (3 * b)
b = (s + 2 * c) / (3 * a)
c = (3 * a * b - s) / 2

Как я могу сгенерировать такие выражения на основе одного исходного выражения?Существуют ли стандартные подходы для решения таких задач?

Ограничения:

1. Набор доступных операторов: +, -, *, /, в том числеунарные + и -
2. операторы *, / и = не могут иметь одну и ту же переменную с обеих сторон (например, s = a * a или s = a + s недопустимы)

Спасибо

Answer 1

См. Сначала: Постфиксная запись в дереве выражений для преобразования вашего RPN в дерево.

Как только вы получите уравнение left expression = right expression, измените его на left expression - right expression = 0 и создайте дерево с left expression - right expression через Маневровый двор и ответ выше. Таким образом, когда вы оцениваете дерево, вы должны получить ответ как 0.

Теперь, основываясь на ваших ограничениях, обратите внимание, что если переменная (скажем, x) неизвестна, результирующее выражение всегда будет иметь вид

(ax + b)/(cx + d) где a, b, c, d будут зависеть от других переменных.

Теперь вы можете рекурсивно вычислять выражение как кортеж (a, b, c, d).

В конце концов, вы в конечном итоге решите линейное уравнение

(ax + b)/(cx + d) = 0 дача x = -b/a

Таким образом, вам не нужно вычислять отдельные выражения для каждой переменной. Достаточно одного дерева выражений. А с учетом других переменных вы просто рекурсивно вычисляете кортеж (a, b, c, d) и в конце решаете линейное уравнение.

(Неполный) псевдокод будет

TupleOrValue Eval (Tree t) {

       if (!t.ContainsVariable) {
           blah;
           return value;
       }

       Tuple result;

       if (t.Left.ContainsVariable) {
            result = Eval(t.Left);  
            value = Eval(t.Right);

            return Compose(t.Operator, result, value);      
       } else {
            result = Eval(t.Right);  
            value = Eval(t.Left);

            return Compose(t.Operator, result, value);      
       }
}

Tuple Compose(Operator op, Tuple t, Value v) {

    switch (op) {

        case 'PLUS': return new Tuple(t.a + v*t.c, t.b + v*t.d, t.c, t.d);
                    // (ax+b)/(cx+d) + v = ( (a + vc)x + b + dv)/(cx + d)
        // blah
    }
}

Например, если выражение x+y-z = 0. Дерево будет

     +
    /  \
   x    -
       / \
       y  z

Для y = 5 и z = 2.

Eval (t.Right) вернет y-z = 3, так как это поддерево не содержит x.

Eval (t.Left) вернет (1,0,0,1), что соответствует (1x + 0)/(0x + 1). Примечание: приведенный выше псевдокод является неполным.

Теперь Compose of (1,0,0,1) со значением 3 даст (1 + 3*0, 0 + 3*1, 0, 1) = (1,3,0,1), что соответствует (x + 3)/(0x + 1).

Теперь, если вы хотите решить эту проблему, вы берете x равным -b/a = -3/1 = -3

---

Я оставлю оригинальный ответ:

В общем это будет невозможно.

Например, рассмотрим выражение

x*x*x*x*x + a*x*x*x*x + b*x*x*x + c*x*x + d*x = e

Получение выражения для x в основном соответствует поиску корней многочлена

x ⁵ + топор ⁴ + bx ³ + cx ² + dx -e

, что в целом оказалось невозможным, если вы хотите использовать +, -, /, * и nth корни. См. Абель Руффини Теорема.

Есть какие-то ограничения, о которых вы забыли упомянуть, которые могут упростить проблему?

Answer 2

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

В общем, если вы начнете с этого символического уравнения:

s = 3 * a * b - 2 * c

и вы добавляете ограничения для s, a и c:

s = ...
a = ...
c = ...

вам нужно применить стандартные законы алгебры для перестановки набора уравнений, чтобы получить то, что вы хотите, в данном случае формулу для b:

b = ...

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

Если все ваши уравнения имеют форму (как, например, ваш пример):

left_hand_side_variable_n = combination_of_variables

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

Если уравнения не являются линейными, то вы, возможно, не сможете найти решение, независимо от того, насколько хороша ваша математика (см. Другие ответы для примеров). В той степени, в которой это возможно, вы можете использовать систему компьютерной алгебры (CAS) для управления формулами. Они делают это, представляя формулы, по существу, как абстрактные синтаксические деревья [математика], а не как RPN, и применяют правила преобразования источника в источник (вы бы назвали эти «правила алгебры» из старшей школы). Обычно они уже имеют довольно большой набор встроенных правил («знание»). Некоторые CAS попытаются решить такие системы уравнений для вас, используя встроенные правила; другие, вы должны сказать, какую последовательность алгебраических законов применять в каком порядке.

Вы также можете использовать решатель ограничений , который представляет собой особый вид системы компьютерной алгебры, ориентированный только на ответ на вопрос, который вы задали, например, «с этим набором ограничений и конкретными значения для переменных, каково значение других переменных? Это очень хорошо, если ваши уравнения следуют формам, для решения которых они предназначены; в противном случае нет гарантии, но это не удивительно.

Можно также использовать систему программной трансформации, которая манипулирует произвольными «деревьями синтаксиса», потому что деревья алгебры являются лишь частным случаем деревьев синтаксиса. Чтобы использовать такую ​​систему, вы определяете язык, которым нужно манипулировать (например, обычную алгебру), и правила, с помощью которых можно манипулировать, а также порядок применения правил. [Учитель сделал именно это для вас в вашем классе вступительной алгебры, но не таким формальным образом] Вот пример моей системы преобразования программ, управляющей алгеброй . Для решения уравнений вам нужны практически те же правила, но другой порядок применения.

Наконец, если вы хотите сделать это в программе на C ++, либо вам нужно смоделировать один из вышеперечисленных более общих механизмов (это огромный объем работы), либо у вас есть узкое, что вы готовы значительно решить ( например, «линейные комбинации»), чтобы вы могли воспользоваться преимуществами гораздо более простого алгоритма.

Answer 3

Существует довольно простое выражение для очень простых выражений (как в вашем примере), где каждая переменная встречается в основном один раз, а каждый оператор является двоичным. Алгоритм - это в основном то, что вы делаете вручную.

Переменная, которую мы ищем, будет x в следующих строках. Преобразуйте свое выражение в форму f(...,x,...) == g(...). Либо переменная x уже находится слева, либо вы просто переключаете обе стороны.

Теперь у вас есть две функции, состоящие из приложений бинарных операторов к подвыражениям, то есть f = o_1(e_1,e_2), где каждый e_i является либо переменной, числом, либо другой функцией e_i = o_i(e_j, e_k). Думайте об этом как двоичное представление дерева, где узлы являются операторами, а листы являются переменными или числами. То же самое относится к g.

Вы можете применить следующий алгоритм (наша цель - преобразовать дерево в дерево, представляющее выражение x == h(...):

while f != x:
    // note: f is not a variable but x is a subexpression of f
    // and thus f has to be of the form binop(e_1, e_2)

    if x is within e_1:
        case f = e_1 + e_2: // i.e. e_1 + e_2 = g
            g <- g - e_2
        case f = e_1 - e_2: // i.e. e_1 - e_2 = g
            g <- g + e_2
        case f = e_1 * e_2: // i.e. e_1 * e_2 = g
            g <- g / e_2
        case f = e_1 / e_2: // i.e. e_1 / e_2 = g
            g <- g * e_2
        f <- e_1
    else if x is within e_2:
        case f = e_1 + e_2: // i.e. e_1 + e_2 = g
            g <- g - e_2
        case f = e_1 - e_2: // i.e. e_1 - e_2 = g
            g <- g + e_2
        case f = e_1 * e_2: // i.e. e_1 * e_2 = g
            g <- g / e_2
        case f = e_1 / e_2: // i.e. e_1 / e_2 = g
            g <- g * e_2
        f <- e_1

Теперь, когда f = x и f = g были сохранены на всех этапах, мы имеем x = g в качестве решения.

На каждом шаге вы гарантируете, что x остается на lhs, и в то же время вы уменьшаете глубину lhs на один. Таким образом, этот алгоритм завершится после конечного количества шагов.

В вашем примере (решите для b):

1. f = 3a*b*2c*- и g = s
2. f = 3a*b* и g = s2c*+
3. f = b и g = s2c*+3a*/

и, следовательно, b = (s + 2*c)/(3*a).

Если у вас больше операторов, вы можете расширить алгоритм, но у вас могут возникнуть проблемы, если они не обратимы.