Zaawansowany kalkulator

28

Musisz napisać program, który ocenia ciąg znaków, który zostałby wprowadzony do zaawansowanego kalkulatora.

Program musi zaakceptować dane wejściowe za pomocą stdin i wydać poprawną odpowiedź. W przypadku języków, które nie mają funkcji akceptujących standard, możesz przejąć funkcje readLinei printobsłużyć te zadania.

Wymagania:

  • Nie używa żadnych funkcji „eval”
  • Obsługuje liczby zmiennoprzecinkowe i liczby ujemne
  • Obsługuje co najmniej operatory +, -, *, / i ^
  • Obsługuje nawiasy i nawiasy do zastępowania normalnej kolejności
  • Obsługuje dane wejściowe zawierające jedną lub więcej spacji między operatorami a liczbami
  • Ocenia dane wejściowe przy użyciu standardowej kolejności operacji

Przypadki testowe

Wkład

10 - 3 + 2

Wydajność

9


Wkład

8 + 6 / 3 - 7 + -5 / 2.5

Wydajność

1


Wkład

4 + [ ( -3 + 5 ) * 3.5 ] ^ 2 - 12

Wydajność

41
Kevin Brown
źródło
1
Czy to w porządku, jeśli .0na końcu są liczby końcowe, jeśli są liczbami całkowitymi? Ponadto: jak dokładny musi być kalkulator (w odniesieniu do precyzji zmiennoprzecinkowej i tym podobnych)?
sepp2k
1
Wyjście może mieć końcowy .0koniec. Nie jestem zbyt pewny precyzji, ale im więcej, tym lepiej.
Kevin Brown,
1
Wersja przepełnienia stosu była ewaluatorem wyrażeń matematycznych (pełna PEMDAS) . Chociaż wiele odpowiedzi na to pytanie to zliczanie linii (?!?). Nadal istnieje kilka zwięzłych odpowiedzi w c.
dmckee,
Bonus dla kalkulatorów PN / RPN?
Mateen Ulhaq,

Odpowiedzi:

8

C ++, 640 583

string k="[]()+-*/^";stack<double> m;stack<char> n;
#define C(o,x,y) ('^'==o?x<y:x<=y)
#define Q(a) double a=m.top();m.pop();
#define R(o) {Q(b)Q(a)m.push(o=='+'?a+b:o=='-'?a-b:o=='*'?a*b:o=='/'?a/b:o=='^'?pow(a,b):0);n.pop();}
while(!cin.eof()){string s;getline(cin,s,' ');if(s.empty())continue;if('\n'==*--s.end())s.erase(--s.end());(s.size()==1&&s.npos!=k.find(s[0]))?({char c=s[0]=='['?'(':s[0]==']'?')':s[0];while(!n.empty()&&'('!= c&&C(c,k.find(c),k.find(n.top())))R(n.top());')'==c?n.pop():n.push(c);}):m.push(strtod(s.c_str(),0));}while(!n.empty())R(n.top());cout<<m.top()<<endl;

Zębaty

string k="[]()+-*/^";
stack<double> m;
stack<char> n;
#define C(o,x,y) ('^'==o?x<y:x<=y)
#define Q(a) double a=m.top();m.pop();
#define R(o) {Q(b)Q(a)m.push(o=='+'?a+b:o=='-'?a-b:o=='*'?a*b:o=='/'?a/b:o=='^'?pow(a,b):0);n.pop();}
while(!cin.eof())
{
    string s;
    getline(cin,s,' ');
    if(s.empty())continue;
    if('\n'==*--s.end())s.erase(--s.end());
    (s.size()==1&&s.npos!=k.find(s[0]))?({
        char c=s[0]=='['?'(':s[0]==']'?')':s[0];
        while(!n.empty()&&'('!= c&&C(c,k.find(c),k.find(n.top())))
            R(n.top());
        ')'==c?n.pop():n.push(c);
    }):m.push(strtod(s.c_str(),0));
}
while(!n.empty())
    R(n.top());
cout<<m.top()<<endl;

Mój pierwszy golfowy kod, więc czekam na komentarze i krytykę!

drspod
źródło
Obsługuje właściwą asocjatywność operatora potęgowania, czego nie wydaje się rozwiązanie Perla JB.
drspod
Ani opis problemu, ani powiązana strona wikipedia nie wspominają o potęgowaniu. Ponadto strona wikipedia wyraźnie mówi, że oba sposoby można znaleźć w komercyjnych kalkulatorach.
JB
1
+1 ładnie grał w golfa, ale ... porzucenie obejmuje, using namespace stda główna funkcja nie jest w porządku, prawda?
przestał się obracać w lewo o
2

PHP - 394 354 312 znaków

<?=e(!$s=preg_split('#\s+#',`cat`,-1,1),$s);function e($P,&$s){$S='array_shift';if(($a=$S($s))=='('|$a=='['){$a=e(0,$s);$S($s);}while($s&&($p=strpos(' +-*/^',$o=$s[0]))&&$p>=$P){$b=e($p+($S($s)!='^'),$s);if($o=='+')$a+=$b;if($o=='-')$a-=$b;if($o=='*')$a*=$b;if($o=='/')$a/=$b;if($o=='^')$a=pow($a,$b);}return$a;}

Zębaty:

<?
preg_match_all('#\d+(\.\d+)?|\S#',`cat`,$m);
$s=$m[0];
function e($P) {
        global $s;
        if (strpos(" ([",$s[0])){
                array_shift($s);
                $a=e(0);
                array_shift($s);
        } else {
                $a=array_shift($s);
                if ($a=='-')$a.=array_shift($s);
        }
        while ($s && ($p=strpos(' +-*/^',$o=$s[0])) && $p >= $P) {
                array_shift($s);
                $b = e($p+($o!='^'));
                switch($o){
                case'+':$a+=$b;break;
                case'-':$a-=$b;break;
                case'*':$a*=$b;break;
                case'/':$a/=$b;break;
                case'^':$a=pow($a,$b);
                }
        }
        return $a;
}
echo e(0);
Arnaud Le Blanc
źródło
2

Postscriptum, 446

Wykorzystuje algorytm stoczni manewrowej.

[/*[/p
2/e{mul}>>/d[/p
2/e{div}>>/+[/p
1/e{add}>>/-[/p
1/e{sub}>>/o[/p
9/e{}>>/c[/p
-1/e{}>>/^[/p
3/e{exp}>>/p
0>>begin/s(%stdin)(r)file 999 string readline pop def
0 1 s length 1 sub{s exch[0 1 255{}for]dup[(\(o)([o)(\)c)(]c)(/d)]{{}forall
put dup}forall
pop
3 copy pop
get
get
put}for{s token not{exit}if
exch/s exch store{cvr}stopped{load
dup/p get
p
le{currentdict end
exch begin/e get exec}{begin}ifelse}if}loop{{e end}stopped{exit}if}loop
=

Nie grał w golfa i skomentował:

% We associate the operators with their precedence /p and the executed commend /e
[
  (*)[/p  2 /e{mul}>>
  (d)[/p  2 /e{div}>> % This is division
  (+)[/p  1 /e{add}>>
  (-)[/p  1 /e{sub}>>
  (o)[/p  9 /e{   }>> % This is open bracket
  (c)[/p -1 /e{   }>> % This is close bracket
  (^)[/p  3 /e{exp}>>
  /p 0
>>begin

% Let's read the input string
/s(%stdin)(r)file 999 string readline pop def

% If we want to use the token operator, we have to replace (, [, ), ] and / to get meaningful results
% We use kind of an encoding array (familiar to PostScripters) to map those codes to o, c, and d.
0 1 s length 1 sub{        % index
  s exch                   % string index
  [0 1 255{}for] dup       % string index translationArray translationArray
  [(\(o)  ([o)  (\)c)  (]c)  (/d)] % string index translationArray translationArray reencodeArray
  {                        % string index translationArray translationArray translationString
    {}forall               % string index translationArray translationArray charCode newCharCode
    put dup                % string index translationArray translationArray
  }forall                  % string index translationArray translationArray
  pop                      % string index translationArray
  3 copy pop               % string index translationArray string index
  get                      % string index translationArray charCode
  get                      % string index translatedCharCode
  put                      % -/-
}for

% Now we can actually start interpreting the string
% We use the stack for storing numbers we read and the dictionary stack for operators that are "waiting"
{                          % number*
  s token not{exit}if      % number* string token
  exch /s exch store       % number* token
  % We try to interpret the token as a number
  {cvr}stopped{            % number* token
    % If interpretation as number fails, we have an operator
    load                   % number* opDict
    % Compare operator precedence with last operator on dictstack
    dup /p get             % number* opDict opPrec
    p                      % number* opDict opPrec prevOpPrec
    le {                   % number* opDict
      % If the last operator on the stack has at least the same precedence, execute it
      currentdict end      % number* opDict prevOpDict
      exch begin           % number* prevOpDict
      /e get exec          % number*
    }{                     % number* opDict
      % If last operator doesn't have higher precedence, put the new operator on the dictstack as well
      begin
    }ifelse
  }if
}loop
% If we're finished with interpreting the string, execute all operators that are left on the dictstack
{{e end}stopped{exit}if}loop
=

DO ZROBIENIA : Właściwa asocjatywność potęgowania

Thomas W.
źródło
Ach ... Dictstack: genialny!
luser droog
Mogę komentować przepływ stosu, więc byłem trochę zdezorientowany. Czy to normalne, że reputacją zarządza się osobno, czy popsułem loginy?
Thomas W.,
Chciałem powiedzieć, że z Twoim rozwiązaniem musi być coś nie tak, ponieważ wszystkie trzy podane powyżej przypadki testowe zawiodły. Jednak nie próbowałem jeszcze zrozumieć, co robisz (niektóre komentarze byłyby fajne ;-)).
Thomas W.
1) Gdy trafisz 200 na dowolnej stronie, zaczniesz od 101 na każdej stronie. Lub kliknij tutaj 50. 2) AUGHH! Myślałem, że to szybkie rozszerzenie Podstawowego kalkulatora. Nawet nie widziałem, że nawiasy są wymagane! I nie przetestowałem tego zbyt dobrze. No cóż; spodnie w dół, przynajmniej moje majtki są czyste!
luser droog
@luserdroog: „@ThomasW” nie zaprasza mnie do komentowania.
Thomas W.,
1

Python 2 , 339 335 bajtów

import re
x,s=input(),re.sub
def f(y):
 y,r=s('- ','+ -',y).split(),['^','*','/','+','-']
 for c in r:
  while c in y:d=y.index(c)-1;a,b=map(float,[y[d],y[d+2]]);y=y[:d]+[((a,-a)[a<0]**b,a*b,a/b,a+b,a-b)[r.index(c)]]+y[d+3:]
 return`y[0]`
w=lambda b:s("[([]+[\d+\-*/^ .]*[)\]]",lambda m:f(m.group()[1:]),s(' +',' ',b))
print f(w(w(x)))

Wypróbuj online!

  • -4 bajty poprzez zmianę str (x) za pomocą backticks ``!
Keerthana Prabhakaran
źródło
0

Postscriptum, 1000 695 665 494

Pomysły na ukradki od ThomasW. Dodano funkcję: akceptuje ciągi znaków ze spacjami lub bez nich wokół operatorów.[funkcja usunięta]


Korzystanie ARGUMENTSjest krótszy niż %stdin, i łatwiejsze do badania, do startu!


Uproszczono podstawianie polegające na zastąpieniu nawiasów parenami.

575(1)10:36 PM:ps 0> gsnd -q -- calc2bg.ps '10 - 3 + 2'
9
576(1)10:37 PM:ps 0> gsnd -q -- calc2bg.ps '8 + 6 / 3 - 7 + -5 / 2.5'
1.0
577(1)10:37 PM:ps 0> gsnd -q -- calc2bg.ps '4 + [ ( -3 + 5 ) * 3.5 ] ^ 2 - 12'
41.0

Kod:

/T[/^[/C{exp}/P 4/X{le}>>/*[/C{mul}/P 3/X{lt}>>/[/C{div}/P
3/X{lt}>>/+[/C{add}/P 2/X{lt}>>/-[/C{sub}/P
2/X{lt}>>>>def[/integertype{}/realtype{}/stringtype{V}/nametype{cvlit/N
exch store{P T N get dup/P get exch/X get exec{exit}if C end}loop T N get
begin}91 40 93 41>>begin/V{0 1 2 index length 1 sub{2 copy get
dup where{exch get}if 3 copy put pop pop}for[/N 0/R 0/P 0/C{}>>begin{token
not{exit}if exch/R exch store dup type exec R}loop{P 0 eq{end exit}if C
end}loop}def ARGUMENTS{V ==}forall

Nie golfił i skomentował:

%!
%Shunting-Yard Algorithm using dictstack for operators
%invoke with %gsnd -q -- calc2bg.ps [ 'expr1' ]*

%The operator table. C:code P:precedence X:test(implements associativity)
/T[
    /^[/C{exp}/P 4/X{le}>>
    /*[/C{mul}/P 3/X{lt}>>
    /[/C{div}/P 3/X{lt}>>
    /+[/C{add}/P 2/X{lt}>>
    /-[/C{sub}/P 2/X{lt}>>
>>def

%The type-dispatch dictionary
%numbers: do nothing
%string: recurse
%name: process op
[%/integertype{}/realtype{} %now uses `where` below
/stringtype{V}/nametype{
pstack()=
    cvlit/N exch store %stash cur-op
    {
        P %prec(tos)
        T N get %prec(tos) cur-op-dict
        dup/P get %prec(tos) cur-op-dict prec(cur-op)
        exch/X get %prec(tos) prec(cur-op) test(cur-op)
        exec{exit}if %exit if prec(tos) < || <= prec(cur-op)
/C load ==
        C %pop-and-apply
        end
pstack()=
    } loop
    T N get begin %push cur-op
}>>begin

%substitutions
[91 40 93 41>>begin %replace brackets with parens
/V {
    %pre-process
    0 1 2 index length 1 sub {
        2 copy get
        dup where { exch get } if
        3 copy put pop pop
    } for
dup ==

    [/N 0/R 0/P 0/C{}>>begin %dummy base operator and storage
    { token not{exit}if exch /R exch store %extract token, stash Remainder
pstack(>)=
        %dispatch type procedure
        dup type dup where { pop exec }{ pop } ifelse
    R }loop
pstack()=
    {
        P 0 eq{end exit}if %hit dummy op: exit
/C load ==
        C end %pop and apply
    } loop
} def

ARGUMENTS{V ==}forall %iterate through the command-line arguments
luser droog
źródło
@ThomasW Zastanawiam się, czy to zadziała, zapraszając do komentowania. (?)
luser droog
Pełniejsze wdrożenie tego samego pomysłu opublikowałem w pliku comp.lang.postscript .
luser droog,