digitron + (ukljucujuci zagrade)... :)

[ vladar85 @ 15.02.2010. 13:33 ] @

Mozhda je pitanje malo bez veze, ali zna li neko neki fin algoritam koji obavlja aritmeticke operacije, ali ukljucujuci mogucnost da se dodaju zagrade u izrazu (naravno prozivljan broj)...??

Na primer da izrachuna neshto trivijalno kao shto je (2+2)*2...

Ne zamerite ako sam postavio glupo pitanje

[ X Files @ 15.02.2010. 15:23 ] @

Na netu bi trebalo da ima dosta o tome (source code, gotovi dll-ovi, programi)
Google: "expression evaluator source code"

Npr:
http://www.arstdesign.com/articles/expression_evaluation.html
http://www.codeproject.com/KB/...onevaluator.aspx?display=Print

E sad zavisi u kom obliku ti treba.

[ Burgos @ 15.02.2010. 15:29 ] @

Najlakše ti je da izraz u infix formi pretvoriš u prefix ili postfix oblik.

(pseudokod sa predavanja dr Tomaševića):

Code:
IN2POST(infix, postfix)
INIT-STACK(S, n)
rank = 0
next = INPUT(infix)
while (next) do
    if (next = operand) then
        OUTPUT(next, postfix)
        rank = rank + 1
    else
        while (not(STACK-EMPTY(S)) and (IPR(next)<=SPR(TOP(S))) do
            x = POP(S)
            OUTPUT(x, postfix)
            rank = rank + R(x)
            if (rank < 1) then
                ERROR(Nepravilan izraz)
            end_if
        end_while
        if (next <> ‘)’ ) then
            PUSH(S, next)
        else
            x = POP(S)
        end_if
    end_if
    next = INPUT(infix)
end_while
while (not(STACK-EMPTY(S))) do
    x = POP(S)
    OUTPUT(x, postfix)
    rank = rank + R(x)
end_while
if (rank < 1) then
    ERROR(Nepravilan izraz)
end_if

Code:
EVAL-EXP(postfix)
INIT_STACK(S, n)
while (not_end_of postfix) do
    x = INPUT(postfix)
    if (x = operand) then
        PUSH(S, x)
    else if (x = un_op) then
            oprnd = POP(S)
            rez = x oprnd
            PUSH(S, rez)
        else if (x = bin_op) then
                oprnd2 = POP(S)
                oprnd1 = POP(S)
                rez = oprnd1 x oprnd2
                PUSH(S, rez)
    end_if
end_while
rez = POP(S)
if (STACK-EMPTY(S)) then    return rez
else
    ERROR(Nepravilan izraz)
end_if

Evo ti i tablica prioriteta i operatora

Code:

operator    ipr    spr    R
+, -             2    2    -1
*, /             3    3    -1
↑             5    4    -1
(             6    0    -
)             1    -    -

strelica označava stepenovanje. Zbog asocijativnosti stepenovanja input-prioritet je veći od stek-prioriteta.
Ako ti je potrebno nešto više o ovome, pogledaj poglavlje u knjizi Strukture Podataka dr Mila Tomaševića.

[ Aleksandar Ružičić @ 15.02.2010. 15:51 ] @

ja to volim da resavam sa recursive-descent parserom, evo pseudo-kod (bez lexera, koji vodi racuna o token promenljivoj):

Code:

function addition()
  number x = multiplication()
  while token is one of ("+", "-") do
     string op = token
     skip_token()   // ovo je deo lexera
     if op == "+" then
       x = x + multiplication()
     else if op == "-" then
       x = x - multiplication()
     end if
  loop
  return x
end function

function multiplication()
  number x = factor()
  while token is one of ("*", "/") do
     string op = token
     skip_token()   // ovo je deo lexera
     if op == "*" then
       x = x * factor()
     else if op == "-" then
       x = x / factor()
     end if
  loop
  return x
end function

function factor()
  number x = 0
  if token == "(" then
     skip_token()
     x = addition()
     if token == ")" then
        skip_token()
     else
        error("Syntax error. Missing closing parenthesis.")
     end if
  else
    x = parseNumber(token)
    skip_token()
  end if
  return x
end function

kada se string tokenizuje (sto radi lexer) poziva se addition() funkcija koja hendluje operatore najnizeg prioriteta.
operacije istog prioriteta se nalaze u istoj funkciji i da bi dobili operande za izvrsavanje operacije pozivaju funkciju koja hendluje operacije viseg prioriteta. (zagrade su recimo operatori najviseg prioriteta)

ovo je po meni dosta citljivije od postfix racunanja i jednostavnije za shvatanje (jer je nekako "prirodan" nacin resavanja problema)

edit:
evo nadjoh jedan svoj prastari kod (u freebasic-u) na tu temu: http://www.streetcds.co.uk/see.tar.gz (to mi je bio jedan od prvih recursive-descent parsera koje sam napisao i ovo je bilo samo testa radi ali mislim da je bas ono sto tebi treba; "advanced calculator")

_{[Ovu poruku je menjao Aleksandar Ružičić dana 15.02.2010. u 17:04 GMT+1]}

[ vladar85 @ 15.02.2010. 20:52 ] @

ja ovo radim pomocu dva steka, stek operatora i stek brojeva. kad se pokusha doda na stek operator manje vazhnosti u odnosu na onaj koji je na vrhu steka operatora taj sa vrha se ponishtava obavljajuci operaciju na dva broja sa vrha steka brojeva broj_2 operator broj_1.

ako se pojavi otvorena zagrada spushta se na stek, ako se pojavi zatvorena smatra se da je najmanjeg prioriteta i sve se pop-uje sa steka operatora i vrshe operacije nad stekom brojeva dok god ne naidje otvorena zagrada, nakon toga se ove dve zagrade ponishtavaju. za operatore kao shto rekoh vazhi klasichno pravilo, ako nailazi operator manje vazhnosti od onog na vrhu steka vrshi se ponishtavanje tog operatora uz aktivnost istog na prva dva broja sa steka brojeva, a procedura se ponavlja dok god ima operatora na vrhu steka koji su veceg prioriteta od nadolazeceg.

kad se predje preko ceo string (izraz) na kraju se prazni stek operatora i dobija tachan rezultat.

Evo primera:

treba reshiti 2*(2+2)

Code:

korak 1:
2
korak 2:
2   *
korak 3, nailazi otvorena zagrada koja je neutralna i samo se spushta na stek operatora:
2   (
    *
korak 4:
2   (
2   *
korak 5:
2   +
2   (
    *
korak 6:
2   +
2   (
2   *
korak 7, poshto je zatvorena zagrada manjeg prioriteta od bilo kog operatora svi operatori koji su manjeg prioriteta od operatora koji zahteva stek bice ponishtetni vrsheci svoju operaciju, a primenom formule drugi_sa_vrha OP prvi_sa_vrha:
     )
-------

4   (
2   *

korak 8, zagrade koje se nadju na steku jedna do druge automatski se ponishtavaju ako je na steku otvorena a nailazi zatvorena:
4   *
2

korak 9, preostali operator na steku operatora se primenjuje nad dva preostala operanda na steku brojeva:
2*4=8

ne znam koliko je ovo efikasan algoritam, ali izbegavamo rekurziju, bukvalno u jednom prolasku kroz izraz reshavamo sve, bez obzira na postojanje zagrada.

Nadam se da sam bio jasan sa ovim algoritmom, dakle ovim izbegavamo potrebu za prevodjenje u poljsku postfiksnu notaciju ili sl.

evo programche ako hoce neko da testira:
http://www.mediafire.com/?fjmyhtm2hhx

_{[Ovu poruku je menjao vladar85 dana 15.02.2010. u 22:18 GMT+1]}