ONP - wyliczanie wartości zmiennej, znając wynik wyrażenia

Question

Witam,

Napisałem program w języku C++, w którym zaimplementowałem drzewo TRIE(do przechowywania zmiennych) oraz algorytmy do konwersji na ONP oraz obliczania wartości wyrażenia w ONP.

Mój program powinien :

1. Obliczyć wartość wyrażenia. - co już mam gotowe.

2. Obliczyć wartość zmiennej, znając wartość wyrażenia, dokładnie chodzi o coś takiego:

WYZNACZ x ( ( x + 1 ) * 2 - ( 3 / 4 ) ) = ( 60 ) 

WYZNACZ x ( ( 1 + 2 ) * 3 - ( x / 4 ) ) = ( 60 )

 Dostałem podpowiedź od wykładowcy, powinienem przekształcać lewą stronę w ten sposób by została tam tylko zmienna X. Czyli najpierw przerzuć -3/4 na prawo = +3/4, potem podzielić przez 2 i odjąć jeden.

Problem w tym, że całe wyrażenie jest w ONP czyli x 1 + 2 * 3 4 / -

W dodatku, podczas wyliczenia czegoś takiego znajdując zmienną (x), odrazu podstawiam wartość, ponieważ cały algorytm obliczający, oparty jest na stosie, którego elementem jest typ DOUBLE.

 

W jaki sposób powinienem wiedzieć, które operacje oraz wartości przenosić? 

Answer 1

(x + 1) * 2 - 3 / 4 = 60

x 1 + 2 * 3 4 / - = 60

przenoszę 3 4 / na prawą stronę równania zmieniając znak:

x 1 + 2 * = 60 3 4 / +

dzielę obustronnie przez 2

x 1 + = 60 3 4 / + 2 /

przenoszę 1 na prawą stronę zmieniając znak

x = 60 3 4 / + 2 / 1 -

obliczam: 3 4 / = 0,75

60 0,75 + = 60,75

60,75 2 / = 30,375

30,375 1 - = 29,375

sprawdzam:

(29,375 + 1) * 2 - 3 / 4 = 30,375 * 2 - 3 / 4 = 60,75 - 0,75 = 60

Comments

Tak wiem o co chodzi, ale jeśli jest inny test, gdzie zmienna występuje w innych nawiasach, w trudniejszym równaniu, to program musiałby jakoś sprawdzić czy ta zmienna w operacji występuje  czy nie. A nie mam pomysłu na to, zwłaszcza, w ONP.

Dla takiego wyrażenia ( ( 1 + 2 ) * 3 - ( x / 4 ) ) = ( 60 ) musiałbym wiedzieć, by przenieść to (1+2)*3. Jak napisać algorytm który rozpoznałby te operacje, które nie są związane z X?

---

Do twoich celów zrobiłbym wersję stosu ze stringami.  Po czym poznać, że (1 + 2)  * 3 można przenieść? Bo pomiędzy częścią gdzie występuje x a tym wyrażeniem jest operator odejmowania (tak samo by było przy dodawaniu). Potrzebujesz dwóch stosów jednego dla lewej strony i jednego dla prawej strony równania.

1 2 + 3 * x 4 / - = 60

Na końcu masz operator odejmowania, pomiędzy 1 2 + 3 * a x 4 /

Reasumując dla dość prostych przypadków równań (takich jak ty podajesz) najpierw musisz dorwać x-sa i znaleźć taką część wyrażenia, która jest oddzielona od reszty operatorem + lub -. Jeżeli takiego nie ma to w grę wchodzą operatory * i /. Oczywiście to jest dość ogólny pogląd tego jak bym mniej więcej starał się za to zabrać. Nie wiem też jak zaawansowane mają być wzory, które chcesz przekształcać. Np. coś takiego (x + 1) / (2 * x) = 60 w ONP to będzie x 1 + 2 x * / = 60 i tu masz już większy problem bo musisz rozbić na dwa ułamki:

x 2 x * / 1 2 x * / + = 60 - teraz powinieneś skrócić pierwszy ułamek

1 2 / 1 2 x * / + = 60 - teraz przenoszenie

1 2 x * / = 60 1 2 / - teraz trzeba zrobić odwrotność

2 x * = 1 60 1 2 / - / a teraz podzielić przez 2

x = 1 60 1 2 / -  / 2 /

Generalnie dość ciekawe zagadnienie i z pewnością nie takie łatwe do ogarnięcia.

---

Na moje szczęście zmienna, której szukam pojawi się po lewej stronie tylko raz.

Na nieszczęście, wzory są dosyć długie, i jest ich sporo 

WYZNACZ de ( ( ( ( ( pc * 8 ) + 9 ) + 7 ) + ( ( ( wd + qd ) / ib ) / de ) ) * ( 1 / me ) ) = ( ( ( 1 - 2 ) + ( ( 5 * dd ) + ( rb - xe ) ) ) + ( ( kd - ( 5 * 3 ) ) / o ) )

 

Póki co dziękuje za wskazówki, zabieram się za poprawki kodu.

 

Tak dla ciekawości, w ostatnich testach jedno polecenie WYZNACZ wrzucone do word'a :D

---

Widzę, że przykładów do testowania ci nie zabraknie. Jak chcesz to możesz sobie ściągnąć za darmo z internetu program wxMaxima, który takie rzeczy robi i testować go dla twoich przykładów (żebyś miał jak sprawdzić, czy twój algorytm poprawnie przekształca wyrażenie), bo ręcznie przekształcanie takiego potworka trochę zajmie a i o pomyłkę nie trudno.

---

Mam dużo testów, dane wejściowe i wyjściowe :-)

zazwyczaj robię tak :

moj_program.exe < test1.in > test1my.out

comp test1.out test1my.out

I wtedy wiem, w którym teście są błędy, i wtedy można sobie debugować :)