Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » Rätselecke » Grundrechenarten Golf

Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: > 1 < [ 2 ]
000
26.11.2008, 16:45 Uhr
Lensflare



Hallo

hier mal wieder eine Idee für ein Golf Rätsel:

zu implementieren ist folgende Funktion

C++:
int f(char *s)
{

}


die eine Zeichenkette wie zum Beispiel "163+57" parst und das Ergebnis als int zurück gibt.

Das Format der Zeichenkette sind zwei beliebig lange Ganzzahlen mit einem der 4 Grundrechenarten-Operatoren dazwischen. Also + - * /

Ich poste meine Anzahl der Zeichen, sobald ich mit der ersten Version fertig bin.

Viel Spass


EDIT:
Bitte ohne atoi(), sonst wird es zu einfach.
Also generell ohne weitere Funktionen zu benutzen
--
Wenn das Gehirn so einfach wäre, dass wir es verstehen könnten, wären wir so einfach, dass wir es nicht verstehen könnten.
(Emerson Pugh Trost)

Dieser Post wurde am 26.11.2008 um 16:51 Uhr von Lensflare editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
001
26.11.2008, 18:45 Uhr
0xdeadbeef
Gott
(Operator)


Ich hab da noch etwas alten Code in der Richtung rumliegen:

C++:
#include <cmath>
#include <iostream>
#include <map>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <string>

struct token {
  enum id_t {
    op_id,
    num_id
  };

  union {
    char op;
    double x;
  } val;
  id_t type;
};

std::string const ops = "+-*/^()";

std::istream &get_token(std::istream &in, token &tok) {
  double x;
  char c;

  if(in >> c) {
    if(ops.find(c) == std::string::npos) {
      in.unget();
      in >> x;
      tok.val.x = x;
      tok.type = token::num_id;
    } else {
      tok.val.op = c;
      tok.type = token::op_id;
    }
  }

  return in;
}

double eval(double x, double y, char op) {
  switch(op) {
  case '+': return x + y;
  case '-': return x - y;
  case '*': return x * y;
  case '/': return x / y;
  case '^': return std::pow(x, y);
  }

  throw std::runtime_error(std::string(1, op));
}

double solve(std::string equation) {
  std::stack<double> num_stack;
  std::stack<char> op_stack;

  std::map<char, int> pcd_map;

  pcd_map['('] = -1;
  pcd_map['+'] = pcd_map['-'] = 0;
  pcd_map['*'] = pcd_map['/'] = 1;
  pcd_map['^'] = 3;

  std::istringstream is;
  token tok;

  is.str(equation);

  while(get_token(is, tok)) {
    switch(tok.type) {
    case token::num_id:
      {
    num_stack.push(tok.val.x);
    break;
      }
    case token::op_id:
      {
    char op1 = tok.val.op;
    if(op1 == '(') {
      op_stack.push('(');
    } else if(op1 == ')') {
      char op2;
      while((op2 = op_stack.top()) != '(') {
        double x, y;

        op_stack.pop();
        x = num_stack.top(); num_stack.pop();
        y = num_stack.top(); num_stack.pop();
        num_stack.push(eval(y, x, op2));
      }
      op_stack.pop();
    } else {
      char op2;
      while(op1 != '^' && // rechtsassoziativ, derzeit hoechste Prioritaet
        op_stack.size() > 0 &&
        ops.find(op2 = op_stack.top()) != std::string::npos &&
        pcd_map[op1] <= pcd_map[op2]) {
        double x, y;

        op_stack.pop();
        x = num_stack.top(); num_stack.pop();
        y = num_stack.top(); num_stack.pop();
        num_stack.push(eval(y, x, op2));
      }
      op_stack.push(op1);
    }
    break;
      }
    }
  }
  while(op_stack.size() > 0) {
    char op = op_stack.top();
    double x, y;

    op_stack.pop();
    x = num_stack.top(); num_stack.pop();
    y = num_stack.top(); num_stack.pop();
    num_stack.push(eval(y, x, op));
  }

  return num_stack.top();
}

int main() {

  std::string equation;

  std::getline(std::cin, equation);

  std::cout << solve(equation) << std::endl;
}


Nicht direkt golfig, hat dafür aber auch keine Probleme mit (3 + 4) * 5^2.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
002
26.11.2008, 19:39 Uhr
Lensflare



ok meine erste Lösung:
221 Zeichen innerhalb der Funktion
--
Wenn das Gehirn so einfach wäre, dass wir es verstehen könnten, wären wir so einfach, dass wir es nicht verstehen könnten.
(Emerson Pugh Trost)
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
003
26.11.2008, 19:56 Uhr
0xdeadbeef
Gott
(Operator)


113. Unter der Annahme, dass Integerdivision gewünscht ist, was angesichts der Signatur eine gerechtfertigte Annahme zu sein scheint.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 26.11.2008 um 20:04 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
004
26.11.2008, 20:06 Uhr
Lensflare



217

jep. Integerdivision ist gefragt

ich muss mir wohl einen anderen Ansatz suchen...

hast du das auch wirklich ohne zusätzliche Funktionen gemacht?
--
Wenn das Gehirn so einfach wäre, dass wir es verstehen könnten, wären wir so einfach, dass wir es nicht verstehen könnten.
(Emerson Pugh Trost)

Dieser Post wurde am 26.11.2008 um 20:09 Uhr von Lensflare editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
005
26.11.2008, 20:13 Uhr
0xdeadbeef
Gott
(Operator)


Jupp. Weitere Funktionen hätten zu viel Platz gefressen.

Nachtrag: Mit Hilfe eines Makros käme ich auf 106.

Nachtrag 2: Frage: Darf s verändert werden?

Nachtrag 3: Ist egal, verändern bringt keine Einsparungen.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 26.11.2008 um 20:24 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
006
26.11.2008, 20:32 Uhr
Lensflare



zu Nachtrag 2:
eigentlich ja. Da wo du es erwähnst, wenn Veränderungen erlaubt sind, dann könnte ich auch noch was einsparen. Ich käme jedoch trotzdem nicht unter 113 :/
--
Wenn das Gehirn so einfach wäre, dass wir es verstehen könnten, wären wir so einfach, dass wir es nicht verstehen könnten.
(Emerson Pugh Trost)
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
007
26.11.2008, 20:37 Uhr
0xdeadbeef
Gott
(Operator)


Ich krieg hier jedenfalls nicht mehr runter. Also:

C++:
int f(char const *s) {
int x=0,y=0,o;for(;*s>47;x=x*10+*s++-48);o=*s++;for(;*s>47;y=y*10+*s++-48);return o-42?o-43?o-45?x/y:x-y:x+y:x*y;
}


Mit Makro wär halt

C++:
#define g(v)for(;*s>47;v=v*10+*s++-48);


...und dann entsprechend ersetzt.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 26.11.2008 um 20:38 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
008
26.11.2008, 20:52 Uhr
Lensflare



den doppelten code für das parsen der beiden zahlen habe ich dadurch vermieden, dass ich diesen vorgang wider von der selben funktion erledigen lasse. also quasi rekursiv.


C++:
int f(char *s) //mit s veränderung
{
    int o=0,l=0,a=0,b=0;
    for(;*s>47&&*s<58;s++)
        l++;
    if(*s) //wenn das erste zeichen, das keine ziffer ist, ein operator ist, ...
    {
        //hier wird das ergebnis des terms berechnet und zurückgegeben
        o=*s;
        *s=0; //die stelle wo der operator ist, eine 0 schreiben, damit die erste zahl geparst werden kann
        a=f(s-l); //erste Zahl parsen
        b=f(s+1); //zweite Zahl parsen
        return o<43?a*b:o<44?a+b:o<46?a-b:a/b;
    }
    //hier angelangt wird nur die Zahl geparst und als int zurückgegeben
    s--;
    for(a=1;b<l;b++,a*=10,s--)
        o+=(*s-48)*a;
    return o;
}


172 Zeichen.
--
Wenn das Gehirn so einfach wäre, dass wir es verstehen könnten, wären wir so einfach, dass wir es nicht verstehen könnten.
(Emerson Pugh Trost)

Dieser Post wurde am 26.11.2008 um 20:57 Uhr von Lensflare editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
009
26.11.2008, 21:00 Uhr
0xdeadbeef
Gott
(Operator)


Hmm...das bringt mich glatt auf eine Idee:

C++:
int f(char const *s) {
int x=0;for(;*s>47;x=x*10+*s++-48);return*s?*s-42?*s-43?*s-45?x/f(s+1):x-f(s+1):x+f(s+1):x*f(s+1):x;
}


100 Zeichen.

C++:
int x=0,o,y;for(;(o=*s++)>47;x=x*10+o-48);return o?y=f(s),o-42?o-43?o-45?x/y:x-y:x+y:x*y:x;


91.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra

Dieser Post wurde am 26.11.2008 um 21:10 Uhr von 0xdeadbeef editiert.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: > 1 < [ 2 ]     [ Rätselecke ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: