Permalänk
Datavetare

Progblemet #10 - miniräknare

Var länge sedan det kördes ett "progblem", inte så mycket p.g.a. brist på tid utan det är helt enkelt svårt att hitta saker som är tillräckligt enkla för att passa detta format men ändå tillräckligt kluriga/roliga för att några ska orka bidra.

Så vad är "progblemet"? Det är lite inspirerat av saker som Benchmark game och LangRef, d.v.s. man löser ett givet problem i en massa olika programmeringsspråk. Varför? Tja, det kan man fråga sig, själv tycker jag det är lite intressant att se hur ett givet problem kan lösas på lite olika sätt och framförallt i olika språk. Är man nybörjare i ett språk kan det vara intressant att se hur andra löser ett problem i det språket.

Är inte helt säker på att detta fungerar i "progblemet", en miniräknare är inte en svår sak men det är inte heller trivialt och det kommer kanske bli lite svåröverskådligt med program som inte bara är några tiotals rader. Men kanske har helt fel på detta, är knappast någon expert på att skriva parsers!

Beskrivning

För att göra så att flera kan delta så definierar jag två nivåer, nivå 1 är en miniräknare som känner till addition och subtraktion av naturliga tal (0 och större).

Exempel

1+2 =3 1+2+3-4 =2

d.v.s om användaren skriver '1+2<ret>' så svara programmet med '=3'.

Nivå 2 är en miniräknare som hanterar alla fyra räknesättet där multiplikation och division beräknas före addition och subtraktion. Man kan också använda parentes för att evaluera addition/subtraktion före division/multiplikation.

Exempel

1+2*3 =7 (1+2)*-3 =-9

För de som känner till Backus-Naur form så kan man få till allt detta med följande syntax

<expr> ::= <term> { <op2> <term> } <term> ::= <fact> { <op1> <fact> } <fact> ::= "(" <expr> ")" | <num> <op1> ::= "*" | "/" <op2> ::= "+" | "-" <num> ::= [ "-" ] <digit> { <digit> } <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Edit: för att uppgiften ska kräva att programmet i sig utför uppdelning av indata och applicering av operationer så lägger jag till följande

Programmet ska innehålla dessa delmoment

d.v.s. input är en sträng, strängen ska delas upp i operationer (*,/,+,-) och heltal, programmet ska slutligen applicera operationen på uttrycket på var sidan om operationen.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Medlem

Hur bulletproof ska koden vara? Räcker den med att den tar exakt den inputen du har skrivit?

Permalänk
Datavetare
Skrivet av Razki:

Hur bulletproof ska koden vara? Räcker den med att den tar exakt den inputen du har skrivit?

Är helt upp till dig, men kanske inte riktigt kvalificerar sig för nivå 1. Kör man nivå 1 finns ju ganska många varianter på hur man kan lösa inläsning av raden och ändå få till det på rätt sätt.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Datavetare

Språk: Go
Nivå: 2

Vad man vill skapa internt i sitt program när man följer en BNF grammatik är ett s.k. abstract syntax tree (AST).

Om jag skriver in '5 + 2 * (3 - 1)' så vill jag att parsning ska resulterar i denna struktur som då är mitt AST

I programmet är varje box representerad av en Expression instans där op fältet är av typen Add, Mul eller Sub och ringarna är instanser av Number. Både Expression och Number implementerar interfacet Evaluator, så man kan anropa Eval() för att värdet ska beräknas.

Har jag Expression{Number{3}, Sub{}, Number{1}} så kommer Eval() att anropa Eval() på LHS (3) och RHS (1) och sedan skicka in resultatet till Sub{} som implementerar interfacet Operator och för typen Sub{} så gör då Apply() 'return lhs - rhs'.

calc.go

package main import ( "bufio" "fmt" "os" "strconv" "strings" "text/scanner" "unicode" ) type Evaluator interface { Eval() int } type Operator interface { Apply(rhs, lhs int) int } // These types is used to map the 'op' member of 'Expressions' to // the correct 'Apply()' body type Mul struct {} type Div struct {} type Add struct {} type Sub struct {} func (op Mul) Apply(lhs, rhs int) int { return lhs * rhs } func (op Div) Apply(lhs, rhs int) int { return lhs / rhs } func (op Add) Apply(lhs, rhs int) int { return lhs + rhs } func (op Sub) Apply(lhs, rhs int) int { return lhs - rhs } type Expression struct { lhs Evaluator op Operator rhs Evaluator } // Implements the 'Evaluator' interface for 'Expression' // Value = lhs.Eval() 'op' rhs.Eval() func (e Expression) Eval() int { return e.op.Apply(e.lhs.Eval(), e.rhs.Eval()) } type Number struct { int } // Implements the 'Evaluator' interface for 'Number' func (n Number) Eval() int { return n.int } func parseOp(s *scanner.Scanner, ops map[rune]Operator) Operator { // Must manually remove whitespace for ops, done automatically // for numbers if unicode.IsSpace(s.Peek()) { s.Next() return parseOp(s, ops) } if op, ok := ops[s.Peek()]; ok { s.Next() return op } return nil } func parseOp1(s *scanner.Scanner) Operator { return parseOp(s, map[rune]Operator{'*': Mul{}, '/': Div{}}) } func parseOp2(s *scanner.Scanner) Operator { return parseOp(s, map[rune]Operator{'+': Add{}, '-': Sub{}}) } // <expr> ::= <term> { <op2> <term> } func parseExpression(s *scanner.Scanner) Evaluator { t1 := parseTerm(s) for s.Peek() != scanner.EOF { op2 := parseOp2(s) if op2 == nil { break } t1 = Expression{t1, op2, parseTerm(s)} } return t1 } // <term> ::= <fact> { <op1> <fact> } func parseTerm(s *scanner.Scanner) Evaluator { f1 := parseFactor(s) op1 := parseOp1(s) for op1 != nil { f1 = Expression{f1, op1, parseFactor(s)} op1 = parseOp1(s) } return f1 } // <fact> ::= "(" <expr> ")" | <num> // <num> ::= [ "-" ] <digit> { <digit> } func parseFactor(s *scanner.Scanner) Evaluator { switch s.Scan() { case scanner.Int: i, _ := strconv.ParseInt(s.TokenText(), 0, 64) return Number{int(i)} case '-': return Number{-parseFactor(s).Eval()} case '(': e := parseExpression(s) if s.Scan() == ')' { return e } } panic("Invalid syntax at token: '" + s.TokenText() + "'") } func parseLine(s *scanner.Scanner) { // Defined a recover handler that catches lines with bad // syntax, recover() returns 'nil' if the line was // successfully parsed defer func () { if r := recover(); r != nil { fmt.Println("###", r) } }() ast := parseExpression(s) fmt.Println("=", ast.Eval()) } func main() { // The bufio.Scanner is used only to cut Stdin into individual lines lineScanner := bufio.NewScanner(os.Stdin) for lineScanner.Scan() { var s scanner.Scanner s.Init(strings.NewReader(lineScanner.Text())) // Configure scanner.Scanner to return integers as // separat tokens and anything else as raw strings s.Mode = scanner.ScanInts | scanner.ScanStrings parseLine(&s) } }

Dold text

Kör programmet så här

$ go run calc.go

För de som använder Linux kan det vara trevligt med lite bättre editeringsmöjligheter, installera paketet rlwrap ('sudo apt-get install rlwrap' på Ubuntu/Debian) och kör sedan

$ rlwrap go run calc.go

programmet har nu historia via piltangenterna, hoppa till början slutet med ctrl-a/ctrl-k, allt finns här

Edit: vet inte, är nog gränsfall vad som kan stoppas in i en post... Men Go ser rätt bra ut med PHP syntax high-light
Jag lärde mig några nya saker i Go så är själv nöjd, har bara gjort nätverksrelaterade saker tidigare.

Förtydligande, gillar själv inte folk som använder förkortningar utan att förklara vad de står för
LHS: left hand side, det som står till vänster om operatorn
RHS: right hand side, det som står till höger om operatorn

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Datavetare

LISP och AST

Tittar man på uttrycket

5 + 2 * (3 - 1)

och sedan AST-trädet

och slutligen fungerar på hur detta skulle se ut i Lisp

(+ (* (- 3 1) 2) 5)

så kan man notera att syntaxen i Lisp är faktiskt att skriva AST-formatet direkt! En möjligt Lisp implementation skulle kunna vara att skriva en funktion som transformerar strängen '5 + 2 * (3 - 1)' till strängen '(+ (* (- 3 1) 2) 5)' och sedan evaluerar den (i Lisp är data kod och kod är data...).

Inget för mig denna gång, inser att detta är ett gyllene tillfälle att lära mig grunderna i lex och yacc, kan vara bra att känna till då jag jobbar dagligen med C-kod. Så blir nog ett andra bidrag av mig också vad det lider.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Medlem

Blir tokig på denna roliga uppgift. Försöker jobba med Stack, men känner inte att jag hanterar den riktigt bra

Dock är det roligt och göra lite annat. Problemet just nu är att få java compilatorn att fatta vad +, -, /, *, (, ) är för något.

Permalänk
Datavetare
Skrivet av Razki:

Blir tokig på denna roliga uppgift. Försöker jobba med Stack, men känner inte att jag hanterar den riktigt bra

Dock är det roligt och göra lite annat. Problemet just nu är att få java compilatorn att fatta vad +, -, /, *, (, ) är för något.

En uppenbar förenkling (uppenbar så fort man börjar testa sin parser) man kan göra är att bestämma att whitespace inte är tillåtet. Whitespace-eliminering är kanske inte den mest fängslande aspekten av uppgiften.

Edit: och inser hur du försöker lösa uppgiften m.h.a en stack, det borde jag ha tänkt på givet att jag tog mig igenom gymnasiet och KTH med en HP48. Blir intressant att se lösningen.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Inaktiv

Vet inte om jag missförstod uppgiften men såhär gjorde jag i python:

while True: question = input() print("=%d" % eval(question))

Permalänk
Medlem

Nej nu ger jag upp denna uppgift. Jobbet får lida lite imorgon :-). Säkert lagt ner 3 timmar med att testa Stack, Switch, Konvertera mellan olika typer, prövat olika vilkor. Men att ta en String input, och splitta upp den i Integers och operators. Usch nej

Däremot är det skoj att sitta med programmering. Tiden rusar på

Permalänk
Medlem

Perl one-liner

En Perl one-liner som fungerar med parenteser etc:

perl -nle "print '=',eval"

...om man nu vill hoppa över utmaningen och bara ha en miniräknare som gör det som önskas

Visa signatur

Intel Core i7 860 @ 2.80GHz | Corsair XMS3 8GB @ 1600MHz | MSI P55-GD65 | XFX Radeon HD 5970 2GB | Samsung SSD 830-Series 256GB | Corsair AX 750W 80+ GOLD | Dell U2711 | Antec P183 | Corsair Hydro Series H50 | Logitech diNovo Edge | Cyborg R.A.T 7

Permalänk

Börja med att avgränsa problemet ordentligt och gör ett flödesschema: ex http://home.fnal.gov/~cheung/embedded-linux/pics/flowchart4.g...
Denna ovan är dock för inputs med en fysisk miniräknare, men du fattar vinken.
För annars är lösningen på ditt problem oändligt många. Tex hur man vill tolka inmatningen.
Det är bara skrattretande hur enorm skillnaden är mellan att göra programmet i C#/Java mot Assembler, och C för den delen.

Permalänk
Medlem

Räknar vi in bash och Linux enviroment i detta? för då är detta lusenkelt med
http://linux.die.net/man/1/bc

Syntax:

bc -l <<< "(1+2)*-3" -9

Skriptet:

#!/bin/bash echo "Expression: "$1"" echo -n "Result: " && bc -l <<< "$1" exit 0

Använding:
skript "uträkning"

calc "(1+2)*-3" Expression: (1+2)*-3 Result: -9

Visa signatur

Arch - Makepkg, not war -||- Gigabyte X570 Aorus Master -||- GSkill 64GiB DDR4 14-14-15-35-1T 3600Mhz -||- AMD 5900x-||- Gigabyte RX6900XT -||- 2x Adata XPG sx8200 Pro 1TB -||- EVGA G2 750W -||- Corsair 570x -||- O2+ODAC-||- Sennheiser HD-650 -|| Boycott EA,2K,Activision,Ubisoft,WB,EGS
Arch Linux, one hell of a distribution.

Permalänk
Datavetare
Skrivet av televerket:

Börja med att avgränsa problemet ordentligt och gör ett flödesschema: ex http://home.fnal.gov/~cheung/embedded-linux/pics/flowchart4.g...
Denna ovan är dock för inputs med en fysisk miniräknare, men du fattar vinken.
För annars är lösningen på ditt problem oändligt många. Tex hur man vill tolka inmatningen.
Det är bara skrattretande hur enorm skillnaden är mellan att göra programmet i C#/Java mot Assembler, och C för den delen.

Nu får ju folk lösa saker precis hur de vill, för egen del är det här mest en sak jag gör för att själv eventuellt lära mig något. Men visst, poängen försvinner en del även om t.ex. Paratroopers Python-lösning faktiskt visar hur man kan utföra en transform från strängen "1+2*10" till talet 21.

Programmet ska innehålla dessa delmoment

d.v.s. input är en sträng, strängen ska delas upp i operationer (*,/,+,-) och heltal, programmet ska slutligen applicera operationen på uttrycket på var sidan om operationen.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Datavetare
Skrivet av Commander:

Räknar vi in bash och Linux enviroment i detta? för då är detta lusenkelt med
http://linux.die.net/man/1/bc

Syntax:

bc -l <<< "(1+2)*-3" -9

Skriptet:

#!/bin/bash echo "Expression: "$1"" echo -n "Result: " && bc -l <<< "$1" exit 0

Använding:
skript "uträkning"

calc "(1+2)*-3" Expression: (1+2)*-3 Result: -9

Dold text

Har börjat titta lite på flex och bison som är GNU-varianterna av lex och yacc. Känns väldigt mycket som bc är ett stor testfall för yacc, är väldigt ett-till-ett i vad man-sidan för bc beskriver och hur man gör saker i yacc

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Medlem

En bra genomgång av detta för C++ finns i Stroustrups The C++ Programming Language, 4th ed. kapitel 10.

Visa signatur

.<

Permalänk

Ok här är mitt försök att få till nivå 1 med lite c++ 11 kod:

#include <iostream> #include <string> #include <vector> #include <sstream> // Tokenize function std::vector<std::string> tokenize(const std::string & str, char delimiter) { std::stringstream ss(str); std::string item; std::vector<std::string> results; while (std::getline(ss, item, delimiter)) { results.push_back(item); } return results; } int convert_to_number(const std::string & str) { int result; if (!(std::istringstream(str) >> result)) { return 0; } return result; } int main(int argv, char ** argc) { // User input as string std::string user_input; std::cin >> user_input; // Tokenize the string and add a the sign to them. std::vector<std::string> items_to_add = tokenize(user_input, '+'); std::vector<std::string> all_items; for (auto tok : items_to_add) { std::string token = '+' + tok; std::vector<std::string> items_to_subtract = tokenize(token, '-'); bool is_first = true; for (auto item : items_to_subtract) { if (is_first) { all_items.push_back(item); is_first = false; } else { std::string subtract_item = '-' + item; all_items.push_back(subtract_item); } } } // Everything is added together because // the numbers are signed. int result = 0; for (auto tok : all_items) { result += convert_to_number(tok); } std::cout << "=" << result << std::endl; }

Kan vara så att jag missförstod något i uppgiften. Kommer att uppdatera med nivå 2 sedan om jag löser den.

Permalänk
Datavetare
Skrivet av Superhepper:

Kunde inte låta bli att göra en Clojure variant, den borde fungera lite som ditt C++ program

calc.clj

(defn op?[c] "Returns whether the character 'c' is an operator" (reduce #(or %1 (= c %2)) false "+-")) (def not-op? (complement op?)) (defn remove-space[s] "Removes all white space from a string" (apply str (filter (comp (complement clojure.string/blank?) str) s))) (defn tokenize[in-str] "Takes a string and returns a list of tokens, '3+2-1' -> ['3' '+' '2' '-' '1']" (loop [s in-str res []] (if (empty? s) res (if (op? (first s)) (recur (rest s) (conj res (first s))) (recur (drop-while not-op? s) (conj res (read-string (apply str (take-while not-op? s))))))))) (defn create-sexp[tokens] "Converts a list of tokes into a S-expression, ['3' '+' '2' '-' '1'] -> (+ 3 2 -1)" (let [gtok (group-by op? tokens) ints (gtok false) ops (conj (lazy-seq (gtok true)) \+)] (conj (lazy-seq (reduce (fn[res [op num="num"]] (conj res (* num (if (= op \+) 1 -1)))) [] (map vector ops ints))) '+))) (doseq [line (line-seq (java.io.BufferedReader. *in*))] (println (str "=" (eval (create-sexp (tokenize (remove-space line)))))))

Dold text

Stegen är,

  • läst input från stdin, t.ex. "1 - 2 + 3"

  • ta bort alla white-space, "1 - 2 + 3 " -> "1-2+3"

  • konvertera strängen till en lista av tokens "1-2+3" -> (1 "-" 2 "+" 3)

  • separera tal och operationer, lägg till "+" som operation för första talet (1 "-" 2 "+" 3) -> (["+" 1] ["-" 2] ["+" 3])

  • skapa en lista med nummer, multiplicera talet med -1 on det är en "-" operation, (["+" 1] ["-" 2] ["+" 3]) -> (1 -2 3)

  • lägg till operationen +, (1 -2 3) -> (+ 1 -2 3)

  • evaluera (+ 1 -2 3) -> 2

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk

Så blev jag klar så att koden klarar nivå två. Koden är verkligen ful men det är väl något man får leva med när experimenterar...

#include <iostream> #include <string> #include <vector> #include <sstream> #include <algorithm> #include <cstring> // Tokenize function std::vector<std::string> tokenize(const std::string & str, char delimiter, bool prefix_delimiter = false) { std::stringstream ss(str); std::string item; std::vector<std::string> results; bool is_first_item = true; while (std::getline(ss, item, delimiter)) { if (prefix_delimiter && !is_first_item) { results.push_back(static_cast<const char *>(&delimiter)); } results.push_back(item); is_first_item = false; } return results; } std::string convert_to_string(int number) { std::ostringstream oss; oss << number; return oss.str(); } int convert_to_number(const std::string & str) { int result; if (!(std::istringstream(str) >> result)) { return 0; } return result; } // If there are any parenthesis in // the string it will return // a vector where the parenthesis is // an element. Ex 2+3*(1-2)+3*(1+2) gives // [2+3*],[(1-2)],[+3*],[(1+2)] std::vector<std::string> paranthesis_tokenizer(const std::string & str) { std::vector<std::string> result; unsigned short nr_of_left_parens = 0; unsigned short nr_of_right_parens = 0; std::size_t pos_for_first_paren = 0; for (std::size_t i = 0; i < str.length(); ++i) { if (str.at(i) == '(') { if (nr_of_left_parens == 0) { result.push_back(str.substr(pos_for_first_paren, i - pos_for_first_paren)); pos_for_first_paren = i; } nr_of_left_parens++; } else if (str.at(i) == ')') { nr_of_right_parens++; if (nr_of_left_parens == nr_of_right_parens) { result.push_back(str.substr(pos_for_first_paren, i - pos_for_first_paren + 1)); pos_for_first_paren=i+1; nr_of_left_parens = 0; nr_of_right_parens = 0; } } } return result; } // Requires a pure_token vector and will conduct multiplication // between elements. std::vector<std::string> do_multiplication(const std::vector<std::string> & tokens) { std::vector<std::string> result; std::vector<std::string>::const_iterator it = tokens.cbegin(); for (; it != tokens.cend(); ++it) { if ((*it).compare("*") == 0) { result.pop_back(); result.push_back(convert_to_string(convert_to_number(*std::prev(it))*convert_to_number(*std::next(it)))); ++it; } else { result.push_back(*it); } } return result; } // Requires a pure_token vector and will conduct division // between elements. std::vector<std::string> do_division(const std::vector<std::string> & tokens) { std::vector<std::string> result; std::vector<std::string>::const_iterator it = tokens.cbegin(); for (; it != tokens.cend(); ++it) { if ((*it).compare("/") == 0) { result.pop_back(); result.push_back(convert_to_string(convert_to_number(*std::prev(it))/convert_to_number(*std::next(it)))); ++it; } else { result.push_back(*it); } } return result; } // Creates a pure_token vector from a string // make sure the stirng does not conatin // any parenthesis. std::vector<std::string> get_pure_tokens(const std::string & str) { std::vector<std::string> result; for (auto subtraction_token : tokenize(str, '-', true)) { for (auto addition_token : tokenize(subtraction_token, '+', true)) { for (auto multiplication_token : tokenize(addition_token, '*', true)) { for (auto division_token : tokenize(multiplication_token, '/', true)) { result.push_back(division_token); } } } } return result; } // conducts calculations on a vector of pure_tokens. std::string calc_pure_tokens(const std::vector<std::string> & tokens) { int result = 0; std::vector<std::string> add_and_sub_tokens = do_multiplication(do_division(tokens)); std::vector<std::string>::const_iterator c_it = add_and_sub_tokens.cbegin(); for (; c_it != add_and_sub_tokens.cend(); ++c_it) { if ((*c_it).compare("-") == 0) { result -= convert_to_number(*std::next(c_it)); } else if (((*c_it).compare("+") == 0)) { result += convert_to_number(*std::next(c_it)); } else if (c_it == add_and_sub_tokens.cbegin()) { result += convert_to_number(*c_it); } } return convert_to_string(result); } // A paren can contain several paren so we want // to convert it to a number. std::string convert_paren_to_number(const std::string & paren_str) { std::string stripped_paren_string = paren_str.substr(1, paren_str.length() - 2); std::vector<std::string> paren_item_vector = paranthesis_tokenizer(stripped_paren_string); if (paren_item_vector.size() != 0) { std::string no_paren_str; for (auto element : paren_item_vector) { if (element[0] == '(') { element = convert_paren_to_number(element); } no_paren_str.append(element); } return calc_pure_tokens(get_pure_tokens(no_paren_str)); } // Here we have single string // something like -4+2*2/2+1 return calc_pure_tokens(get_pure_tokens(stripped_paren_string)); } int main(int argv, char ** argc) { // User input as string std::string user_input; std::cin >> user_input; // Remove white spaces user_input.erase(remove_if(user_input.begin(), user_input.end(), isspace), user_input.end()); // create a vector // which contains elements // encapsulated by parentheses. // 5+2*(1-3*(4-3)+2*(2-1))-3*(2-1) will // look something like // [5+2*] // [(1-3*(4-3)+2*(2-1))] // [-3*] // [(2-1)] std::string altered_user_input; std::vector<std::string> paren_item_vector = paranthesis_tokenizer(user_input); if (!paren_item_vector.empty()) { for (auto item : paren_item_vector) { if (item[0] == '(') { item = convert_paren_to_number(item); } altered_user_input.append(item); } } else { altered_user_input = user_input; } std::cout << "=" << calc_pure_tokens(get_pure_tokens(altered_user_input)) << std::endl; }

Permalänk
Medlem

En variant i F# med lätt modifierad syntax.

Ett par förändringar för att tillåta uttryck som 1 + 2 + 4 utan parenteser ---2, -(2) och förbjuda 03 som siffra. Mycket möjligt att detta är helt fel (både i avsikt och utförande, rätta gärna).

Implementationen misslyckas med det sista då lexern äter 03 in till token Number(3) utan gnäll i övrigt så är kodens korrekthet bevisad m.h.a "testade ett par uttryck och det verkade fungera"-strategin.

Edit:
Fixade BNF-syntaxen så att 0 blir tillåtet.
Fixade koden så att den följer reglerna för parsning av nummer.
Lade till en C++-variant också. Den bygger på Stroustrups men med ett mer explicit syntaxträd.

F#

(* <expr> ::= <term> { <op2> <expr> } <term> ::= <fact> { <op1> <term> } <fact> ::= { <opu> } <num> | "(" <expr> ")" <op2> ::= "+" | "-" <op1> ::= "*" | "/" <opu> ::= "-" { <opu> } <num> ::= "0" | <first_digit> <first_digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" { <digit> } <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" { <digit> } *) exception BadCharacter exception BadLexicalTokenStream type LexicalToken = | Number of int | Multiply | Divide | Plus | Minus | ParenthesisLeft | ParenthesisRight let rec digits_to_value (digits:int list) pos_val total = match digits with |[] -> total |v::tail -> digits_to_value tail (pos_val * 10) (total + (v*pos_val)) let rec read_number_rec (text : string) numbers = if (text.Equals("")) then digits_to_value numbers 1 0,"" else let first,rest = text.[0],text.Substring(1) match first with |'0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9' -> read_number_rec rest (int(first) - int('0')::numbers) |_ -> digits_to_value numbers 1 0, text let read_number (text:string) numbers = match numbers with |0::[] -> if(text.Length > 0) then match text.[0] with |'0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9' -> raise BadCharacter |_ -> 0,text else 0,text |_ -> read_number_rec text numbers let rec lex (text : string) = if (text.Equals("")) then [] else let first,rest = text.[0],text.Substring(1) match first with |'0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9' -> let value,rest_after_number = read_number rest [int(first) - int('0')] Number(value) :: lex rest_after_number |'(' -> ParenthesisLeft :: lex rest |')' -> ParenthesisRight :: lex rest |'*' -> Multiply :: lex rest |'/' -> Divide :: lex rest |'-' -> Minus :: lex rest |'+' -> Plus :: lex rest |' '|'\t' -> lex rest // ignore whitespace | _ -> raise BadCharacter type Expression = | Term of Term | Operator2 of Operator2 and Term = | Fact of Fact | Operator1 of Operator1 and Fact = | UnaryOperator of UnaryOperator | Number of Number | ParenthesisExpression of Expression and UnaryOperator = |Minus of Fact and Operator1 = | Multiply of Fact * Term | Divide of Fact * Term and Operator2 = |Add of Term * Expression |Subtract of Term * Expression and Number = Number of int let rec evaluate (expression : Expression) = match expression with |Term(term) -> ev_term term |Operator2(op2) -> ev_operator2 op2 and ev_term (term:Term) = match term with |Fact(fact) -> ev_fact fact |Operator1(op1) -> ev_operator1 op1 and ev_fact (fact:Fact) = match fact with |UnaryOperator(opu) -> ev_unaryop opu |Fact.Number(number) -> ev_number number |ParenthesisExpression(expr) -> (evaluate expr) and ev_number (number:Number) = match number with |Number(num) -> num and ev_unaryop (opu : UnaryOperator) = match opu with |Minus(fact) -> -(ev_fact fact) and ev_operator1 (op1 : Operator1) = match op1 with |Multiply(fact,term) -> (ev_fact fact) * (ev_term term) |Divide(fact,term) -> (ev_fact fact) / (ev_term term) and ev_operator2 (op2: Operator2) = match op2 with |Add(term,expr) -> (ev_term term) + (evaluate expr) |Subtract(term,expr) -> (ev_term term) - (evaluate expr) let rec parse (tokens : LexicalToken list) : Expression = match gobble_expression tokens with |expr,[] -> expr |_ -> raise BadLexicalTokenStream and gobble_expression (tokens : LexicalToken list) : Expression * (LexicalToken list) = let term,remaining_tokens = gobble_term tokens match remaining_tokens with |LexicalToken.Plus :: tokens_left -> let righthand_expression,remaining_tokens_left = gobble_expression tokens_left Expression.Operator2(Operator2.Add(term,righthand_expression)),remaining_tokens_left |LexicalToken.Minus :: tokens_left -> let righthand_expression,remaining_tokens_left = gobble_expression tokens_left Expression.Operator2(Operator2.Subtract(term,righthand_expression)),remaining_tokens_left |_ -> Expression.Term(term),remaining_tokens and gobble_term (tokens : LexicalToken list) : Term * (LexicalToken list) = let fact,remaining_tokens = gobble_fact tokens match remaining_tokens with |LexicalToken.Divide :: tokens_left -> let righthand_term,remaining_tokens_left = gobble_term tokens_left Term.Operator1(Operator1.Divide(fact,righthand_term)),remaining_tokens_left |LexicalToken.Multiply :: tokens_left -> let righthand_term,remaining_tokens_left = gobble_term tokens_left Term.Operator1(Operator1.Multiply(fact,righthand_term)),remaining_tokens_left |_ -> Term.Fact(fact),remaining_tokens and gobble_fact (tokens : LexicalToken list) : Fact * (LexicalToken list) = match tokens with |LexicalToken.Minus :: tokens_left -> // Eat a negated fact let negated_fact,tokens_remainder = gobble_fact tokens_left Fact.UnaryOperator(UnaryOperator.Minus(negated_fact)),tokens_remainder |LexicalToken.ParenthesisLeft :: tokens_left -> // Eat a paren. expr. let expr,tokens_remainder = gobble_expression tokens_left match tokens_remainder with |LexicalToken.ParenthesisRight :: whatever_tokens_are_left -> Fact.ParenthesisExpression(expr),whatever_tokens_are_left |_ -> raise BadLexicalTokenStream |LexicalToken.Number(num) :: tokens_left -> // Eat a number Fact.Number(Number(num)),tokens_left |_ -> raise BadLexicalTokenStream let calc (progblem:string) = progblem |> lex |> parse |> evaluate

Dold text

C++

#include <iostream> #include <string> #include <sstream> /* <expr> ::= <term> { <op2> <expr> } <term> ::= <fact> { <op1> <term> } <fact> ::= { <opu> } <num> | "(" <expr> ")" <op2> ::= "+" | "-" <op1> ::= "*" | "/" <opu> ::= "-" { <opu> } <num> ::= "0" | <first_digit> <first_digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" { <digit> } <digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" { <digit> } */ using namespace std; enum class tokentype { number, plus, minus, multiply, divide, parenthesis_left, parenthesis_right, end }; enum class expressiontype { term, add, subtract }; enum class termtype { fact, multiply, divide }; enum class facttype { number, parenthesis_expression, negated_fact }; struct token; class tokenstream; class expression; class term; class fact; ostream & operator<< (ostream & out, token const& t); ostream & operator<< (ostream & out, expression const& e); expression * eat_expression(tokenstream & ts); term * eat_term(tokenstream & ts); fact * eat_fact(tokenstream & ts); struct token { tokentype type; double value; token(tokentype const & tt) : type{ tt } {} }; class tokenstream { public: tokenstream(istream & s) : ip{ &s }, owns{ false } {} tokenstream(istream * p) : ip{ p }, owns{ true } {} ~tokenstream() { close(); } token get(); token const& current() { return ct; } void set_input(istream & s) { close(); ip = &s; owns = false; } void set_input(istream * p) { close(); ip = p; owns = true; } private: void close() { if (owns) { delete ip; } } istream* ip; bool owns; token ct{ tokentype::end }; }; class expression { public: expression(expressiontype et, term * t) : type{ et }, term{ t } {} expression(expressiontype et, term * t, expression * e) : type{ et }, term{ t }, expr{ e } {} double operator()() const; ~expression(); private: expressiontype type; term * term; expression * expr; }; class term { public: term(termtype tt, fact * f) : type{ tt }, fact{ f } {} term(termtype tt, fact * f, term * t) : type{ tt }, fact{ f }, op_term{ t } {} double operator()() const; ~term(); private: termtype type; fact * fact; term * op_term; }; class fact { public: fact(facttype ft, double d) : type{ ft }, number{ d } {} fact(facttype ft, expression * e) : type{ ft }, expr{ e } {} fact(facttype ft, fact * f) : type{ ft }, negated_fact{ f } {} double operator()() const; ~fact(); private: facttype type; double number; expression * expr; fact * negated_fact; }; ostream & operator<< (ostream & out, token const& t) { switch (t.type) { case tokentype::number: out << "Number(" << t.value << ")"; break; case tokentype::plus: out << "PLUS"; break; case tokentype::minus: out << "MINUS"; break; case tokentype::multiply: out << "MULT"; break; case tokentype::divide: out << "DIV"; break; case tokentype::parenthesis_left: out << "PAREN_L"; break; case tokentype::parenthesis_right: out << "PAREN_R"; break; case tokentype::end: out << "END"; break; } return out; } ostream & operator<< (ostream & out, expression const* e) { out << "=" << (*e)() << endl; return out; } token tokenstream::get() { char ch = 0; do { if (!ip->get(ch)) { return ct = token{ tokentype::end }; } } while (ch != '\n' && isspace(ch)); switch (ch) { case '\n': case 0: return ct = token{ tokentype::end }; case '*': return ct = token{ tokentype::multiply }; case '/': return ct = token{ tokentype::divide }; case '+': return ct = token{ tokentype::plus }; case '-': return ct = token{ tokentype::minus }; case '(': return ct = token{ tokentype::parenthesis_left }; case ')': return ct = token{ tokentype::parenthesis_right }; case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': case '.': { token tmp{ tokentype::number }; ip->putback(ch); *ip >> tmp.value; return ct = tmp; } default: cerr << "error: bad token" << endl; return ct = token{ tokentype::end }; } } void print_token_stream(tokenstream &ts) { cout << "Token_stream: "; if (ts.current().type == tokentype::end) { cout << ts.current(); ts.get(); } while (ts.current().type != tokentype::end) { cout << " " << ts.current(); ts.get(); } cout << " " << ts.current() << endl; } expression::~expression() { delete term; switch (type) { case expressiontype::add: case expressiontype::subtract: delete expr; break; default: break; } } term::~term() { switch (type) { delete fact; case termtype::multiply: case termtype::divide: delete op_term; default: break; } } fact::~fact() { switch (type) { case facttype::parenthesis_expression: delete expr; break; case facttype::negated_fact: delete negated_fact; break; default: break; } } expression * parse(tokenstream & ts) { ts.get(); return eat_expression(ts); } expression * eat_expression(tokenstream & ts) { auto term = eat_term(ts); switch (ts.current().type) { case tokentype::plus: { ts.get(); return new expression{ expressiontype::add, term, eat_expression(ts) }; } case tokentype::minus: { ts.get(); return new expression{ expressiontype::subtract, term, eat_expression(ts) }; } default: return new expression{ expressiontype::term, term }; } } term * eat_term(tokenstream & ts) { auto fact = eat_fact(ts); switch (ts.current().type) { case tokentype::multiply: { ts.get(); auto righthand_term = eat_term(ts); return new term{ termtype::multiply, fact, righthand_term }; } case tokentype::divide: { ts.get(); auto righthand_term = eat_term(ts); return new term{ termtype::divide, fact, righthand_term }; } default: return new term{ termtype::fact, fact }; } } fact * eat_fact(tokenstream & ts) { switch (ts.current().type) { case tokentype::number: { auto num = ts.current().value; ts.get(); return new fact{ facttype::number, num }; } case tokentype::minus: ts.get(); return new fact{ facttype::negated_fact, eat_fact(ts) }; case tokentype::parenthesis_left: { ts.get(); auto expr = eat_expression(ts); if (ts.current().type == tokentype::parenthesis_right) { ts.get(); return new fact{ facttype::parenthesis_expression, expr }; } } default: cerr << "bad token: " << ts.current().type << endl; throw exception("bad token"); } } // evaluators double expression::operator()() const { switch (type) { case expressiontype::term: return (*term)(); case expressiontype::add: return (*term)() + (*expr)(); case expressiontype::subtract: return (*term)() - (*expr)(); } } double term::operator()() const { switch (type) { case termtype::fact: return (*fact)(); case termtype::multiply: return (*fact)() * (*op_term)(); case termtype::divide: return (*fact)() / (*op_term)(); } } double fact::operator()() const { switch (type) { case facttype::number: return number; case facttype::parenthesis_expression: return (*expr)(); case facttype::negated_fact: return -(*negated_fact)(); } } int main(int argc, char* argv []) { string s; cin >> s; auto expr = parse(tokenstream{ stringstream{s} }); cout << expr << endl; system("pause"); return 0; }

Dold text
Visa signatur

.<

Permalänk
Medlem

[QUOTE=Yoshman;14736313]Kunde inte låta bli att göra en Clojure variant, den borde fungera lite som ditt C++ program

calc.clj

(defn op?[c] "Returns whether the character 'c' is an operator" (reduce #(or %1 (= c %2)) false "+-")) (def not-op? (complement op?)) (defn remove-space[s] "Removes all white space from a string" (apply str (filter (comp (complement clojure.string/blank?) str) s))) (defn tokenize[in-str] "Takes a string and returns a list of tokens, '3+2-1' -> ['3' '+' '2' '-' '1']" (loop [s in-str res []] (if (empty? s) res (if (op? (first s)) (recur (rest s) (conj res (first s))) (recur (drop-while not-op? s) (conj res (read-string (apply str (take-while not-op? s))))))))) (defn create-sexp[tokens] "Converts a list of tokes into a S-expression, ['3' '+' '2' '-' '1'] -> (+ 3 2 -1)" (let [gtok (group-by op? tokens) ints (gtok false) ops (conj (lazy-seq (gtok true)) \+)] (conj (lazy-seq (reduce (fn[res [op num="num"]] (conj res (* num (if (= op \+) 1 -1)))) [] (map vector ops ints))) '+))) (doseq [line (line-seq (java.io.BufferedReader. *in*))] (println (str "=" (eval (create-sexp (tokenize (remove-space line)))))))

Dold text

Stegen är,

  • läst input från stdin, t.ex. "1 - 2 + 3"

  • ta bort alla white-space, "1 - 2 + 3 " -> "1-2+3"

  • konvertera strängen till en lista av tokens "1-2+3" -> (1 "-" 2 "+" 3)

  • separera tal och operationer, lägg till "+" som operation för första talet (1 "-" 2 "+" 3) -> (["+" 1] ["-" 2] ["+" 3])

  • skapa en lista med nummer, multiplicera talet med -1 on det är en "-" operation, (["+" 1] ["-" 2] ["+" 3]) -> (1 -2 3)

  • lägg till operationen +, (1 -2 3) -> (+ 1 -2 3)

  • evaluera (+ 1 -2 3) -> 2

[/QUOTE]

OMG du måste ju ha mellanrum mellan alla forms, dvs inte skriva argumentlistan direkt efter funktionsnamnet! Sjukt inkonsekvent.

Permalänk
Datavetare
Skrivet av tufflax:

OMG du måste ju ha mellanrum mellan alla forms, dvs inte skriva argumentlistan direkt efter funktionsnamnet! Sjukt inkonsekvent.

Nej, man måste inte har mellanrum mellan alla forms och jag är helt konsekvent att inte ha det mellan funktionsnamn och argument. Däremot kommer jag nu ihåg att det normalt att ha det i Clojure (tack vare ditt subtila påpekade ). Har bevisligen glömt rätt mycket i det språket eftersom jag inte hittat något vettigt man kan använda det till. Sedan är det väl Clojure som är inkonsekvent då argument inte är en lista som (nästan) allt annat.

Höll på rätt mycket med Clojure för några år sedan då det i teorin är riktigt bra för "concurrent progamming" men tyvärr är det närapå värdelöst till detta i praktiken p.g.a. usel skalning över CPU-kärnor och allt för komplicerad modell för I/O när man har många samtida kontext. Är också därför jag stark gillar Go, det hanterar "concurrent programming" både i teori och i praktik + att jag personligen föredrar statiskt typade språk över dynamiskt typade.

Edit: Inte så att jag säger att Clojure är generellt dåligt, tvärt om är det ett riktigt trevligt språk. Det var däremot inte bra på det jag ville använda det till.

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Medlem

Kul!
Jag har aldrig fått tummen ur att göra en miniräknare. De fallen det har behövts så har jag kört genvägen att låta andra inbyggda kontroller eller funktioner evaluera stränguttrycket.
Jag hade tänkt att göra det i C# men ett litet problem är att man skulle vilja göra det med generics och samtidigt vara kompatibelt med olika datatyper (uint, long, double, decimal, osv). Problemet i dagsläget är att C# inte har stöd för detta (Det finns exempel inte "public class MathNode<T> where T : Numeric"). Får klura på hur man ska lösa det på annat sätt. Det enda jag kan komma på, på rak arm, är att man gör olika implementationer baserat på vad det är för datatyp.... även om det är drygt.

Att göra det med naturliga tal är ju en bra början iaf.

Visa signatur

ηλί, ηλί, λαμά σαβαχθανί!?

Permalänk
Medlem

Lyckades inte lösa problemet inatt men här är i alla fall en snabb lösning som baserar sig på dijkstras 2 stacks algorigm.
Funkar vad jag vet så länge men inte har flera operationer inanför en parentes.

C++:

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <sstream>

#include <ctype.h>

using namespace std;

std::stack<char> oper;
std::stack<int> vals;

//todo stöd för långa värden
//splita till fler funktioner

bool String2Int(const std::string& str, int& result) // bra string to int from the interwebs
{
std::istringstream ss(str);
ss.imbue(std::locale::classic());
ss >> result;
return !ss.fail() && ss.eof();
}

void domath()
{
// popa operatorn och de senaste värdena
char c = oper.top();
oper.pop();

int a, b;

a = vals.top();
vals.pop();

b = vals.top();
vals.pop();

switch(c)
{
case '*':
vals.push(a*b);
break;
case '+':
vals.push(a+b);
break;
case '-':
vals.push(a-b);
break;
case '/':
vals.push(a/b);
break;

}

}

int calculate(string exp)
{
for(int i = 0; i < exp.length(); i++)
{
if(isalpha(exp[i]))
break;
//todo implementera variabler

if (isdigit(exp[i]))
{
// lägg numret på nummer stacken

int num;
string temp="";

for(int j = i; j < exp.length(); j++)
{
if(isdigit(exp[j]))
{
temp += exp[j];
}
else
{
i = j-1;
break;
}
}

String2Int(temp, num);
vals.push(num);

}else
{
if(exp[i] == '(' || exp[i] == ' ')
NULL;//gör inget
else if( exp[i] == ')')
{
domath();
}else
{
// lägg operator på operator staken
oper.push(exp[i]);
}
}

}

if(vals.size() > 1)
{
while(vals.size() > 1 && oper.size() > 0)
{
//om några operationer är kvar gör dem
domath();
}
}

return vals.top();

}

int main(int argc, _TCHAR* argv[])
{
string s;
cin>>s;

cout << calculate(s);

return 0;
}

Dold text
Visa signatur

KTH student, programmerare, arch användare

Permalänk
Datavetare

Har varit lite ut-swappad då jag var tvungen att läsa in mig rejält på USB (måste skriva en drivare).

Men har i alla fall svängt ihop en variant som använder lex och yacc, eller i mitt fall flex och bison som är GNU-varianterna av dessa verktyg. Man kan nog konstatera att det blev ganska mycket lättare när man använder "rätt" verktyg för jobbet...

Det är två (tre om man räknar Makefile) filer man behöver skriva själv, dels den fil som ska dela upp indata i en ström av tokens, dels den fil som ska verifiera att strömmen av tokens uppfyller den syntax man specificerat. I mitt fall har jag kallat filerna tok.lex och parse.y.

Arbetsflödet för att komma till en körbar fil är detta

tok.lex

%{ #include <stdlib.h> #include "y.tab.h" %} DIGIT [0-9] NUMBER {DIGIT}+ OP [-+*/()\n] SPACE [ \t] %% {NUMBER} { yylval = atoi(yytext); return INTEGER; } {OP} return *yytext; {SPACE} /* Ignore whitespace */ ; . yyerror("invalid character");

Dold text

parse.y

%{ #include <stdio.h> void yyerror(const char *); %} %token INTEGER /* * Precedence rules, evaluate '*' and '/' before '+' and '-', all of * them are left associative */ %left '+' '-' %left '*' '/' %% program: | program expr '\n' { printf("=%d\n", $2); } ; expr: INTEGER { $$ = $1; } | expr '+' expr { $$ = $1 + $3; } | expr '-' expr { $$ = $1 - $3; } | expr '*' expr { $$ = $1 * $3; } | expr '/' expr { $$ = $1 / $3; } | '(' expr ')' { $$ = $2; } ; %% int yywrap(void) { /* Done when seeing EOF */ return 1; } void yyerror(const char *s) { fprintf(stderr, "%s\n", s); } int main(void) { return yyparse(); }

Dold text

Makefile

calc: y.tab.h y.tab.c lex.yy.c $(CC) -o$@ $^ y.tab.c: y.tab.h y.tab.h: parse.y $(YACC) -d $^ lex.yy.c: tok.lex $(LEX) $^ clean: rm -f *.c *.h calc *~

Dold text

Ska ta och sätta mig in i xobust och oelrich varianter (även om mina kunskaper i F# är väldigt grundläggande). Har läst att funktionella språk och specifikt Haskell ska vara väldigt trevliga att skriva parsers i, frågan är om de ändå är lika enkla som det var i yacc/lex?

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk

Kan man inte göra det i Java med hjälp av regular expressions. Man hittar först parenteser och ränkar ut dessa och sedan hittar man multiplikationer och räknar ut dessa.

Exempel:
9*(8+4)/4-1
9*(8+4)/4-1 -> 9*12/4-1
9*12/4-1 -> 108/4-1
108/4-1 -> 27-1
27-1 -> 26

Det går ut på att regex-matcha i räkneordningen och räkna ut det man regex-matchar ända tills inga operatorer finns kvar.

Visa signatur

Stationär: CPU: Intel i5 4690k GPU: ASUS Strix GTX 970 4GB Moderkort: Asus Maximus VII Ranger RAM: Crucial Ballistix Sport 2x8GB Chassi: NZXT H440 CPU-kylare: Corsair H80i PSU: EVGA SuperNOVA G2 750W SSD: Samsung 850 Evo 256GB
Laptop: MacBook Pro 15", late 2016
Programspråk: Java, C++, Python, PHP, Javascript
Hemsida: http://jmcsocial.com

Permalänk
Medlem

Jag har varken den kortaste eller bästa eller snyggaste lösningen (IsLeftPrec är verkligen inte snygg..) men det är en fungerande lösning (med hjälp av Shunting yard algoritmen) i C#.

StackCalc.cs

using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; namespace StackCalc { internal class Program { private static readonly Stack _operatorStack = new Stack(); private static readonly Queue _outputQueue = new Queue(); private static readonly string[] _opperators = {"+", "-", "*", "/", "^"}; private static void Main(string[] args) { while (true) { Console.Write("Enter expression to be evaluated:"); string expression = Console.ReadLine(); string[] tokens = Tokenizer(expression); ConvertToInfix(tokens); EvaluateTheQueue(); Console.WriteLine("=" + _operatorStack.Pop()); } } private static void ConvertToInfix(IEnumerable<string> tokens) { _outputQueue.Clear(); _operatorStack.Clear(); foreach (string token in tokens) { int res; if (int.TryParse(token, out res)) { _outputQueue.Enqueue(res); } else if (_opperators.Contains(token)) { if (_operatorStack.Count != 0) { while (_opperators.Contains(_operatorStack.Peek().ToString()) && IsLeftPrec(token, _operatorStack.Peek().ToString())) { _outputQueue.Enqueue(_operatorStack.Pop()); } } _operatorStack.Push(token); } else if (token == "(") { _operatorStack.Push(token); } else if (token == ")") { while (_operatorStack.Peek().ToString() != "(") { _outputQueue.Enqueue(_operatorStack.Pop()); } _operatorStack.Pop(); } } while (_operatorStack.Count != 0) { _outputQueue.Enqueue(_operatorStack.Pop()); } } private static void EvaluateTheQueue() { _operatorStack.Clear(); while (_outputQueue.Count != 0) { object token = _outputQueue.Dequeue(); if (_opperators.Contains(token)) { int inta = int.Parse(_operatorStack.Pop().ToString()); int intb = int.Parse(_operatorStack.Pop().ToString()); int res; switch (token.ToString()) { case "+": res = inta + intb; _operatorStack.Push(res); break; case "-": res = inta - intb; _operatorStack.Push(res); break; case "*": res = inta*intb; _operatorStack.Push(res); break; case "/": res = inta/intb; _operatorStack.Push(res); break; case "^": res = (int) Math.Pow(inta, intb); _operatorStack.Push(res); break; } } else { _operatorStack.Push(token); } } if (_operatorStack.Count == 1) { } else { throw new Exception("Error in input"); } } private static bool IsLeftPrec(string o1, string o2) { if (o1 != "^") { if ((o1 == "+" || o1 == "-") && (o2 == "*" || o2 == "/" || o2 == "^" || o2 == "+" || o2 == "-") || ((o1 == "/" || o1 == "*") && (o2 == "^" || o2 == "*" || o2 == "/")) || ((o1 == "+" || o1 == "-") && (o2 == "*" || o2 == "/" || o2 == "^")) || ((o1 == "*" || o1 == "/") && (o2 == "^"))) { return true; } } return false; } private static string[] Tokenizer(string input) { var regex = new Regex(@([\+\-\*\(\)\^\/])); return regex.Split(new string(input.Where(c => !Char.IsWhiteSpace(c)).ToArray())); } } }

Visa signatur

CPU: Intel Core i5 4770k @~4.3Ghz GPU: Zotac GTX 970 SLi Nättagg:Corsair AX 1200W 80+ Gold Chassi: Define R4 SSD: Intel SSD 520 240gb RAM: 4xCorsair XMS3 1600MHz

Permalänk
Medlem

Min lösning i C# följer ingen speciell vedertagen algoritm utan har bara försökt lösa det (aka naivt och brute force)
Har försökt hålla den så objektorienterad som möjligt med operatorer och liknande samt att försöka visuellt göra så som det stod i instruktionerna, men det finns mer att göra. Det krävs optimeringar också. Satt igår kväll och försökte hitta något system eller datastruktur för att lösa problemet och detta är vad jag kom fram till.

Har stöd för positiva och negativa decimaltal (double).
Addition (+), Subtraktion (-), Multiplikation (*), Division (/), Modulus (%) och Roten ur (s)
Har även lagt in smågrejer som stöd för att automatiskt tolka "5(5-10)" som "5 * (5 - 10)"
Har inte tagit någon speciell hänsyn till validering av input än.

Det kan vara mycket kod och jag har inte kommenterat det. Så jag kommenterar lite i ett block här istället.

Ex: 5.1 + ((2.2 * 3.3) + (s(9) ^ 2.4) - 5(2.5 - (-1.6))) % 11
Resultat: 5.8266101652382343
Test: Wolframalpha

Vad som händer är att först parsas texten, inte speciellt vackert. Har aldrig lyckats göra en snygg parsning. Blir alltid ett rejält svårtolkat meck.
Hela texten blir en Sequence, varje Sequence har en egen länkad lista
Varje tal blir ett Argument, varje operator blir en Operator, stöter man på en startparentes så skapas det en till Sequence.
Arguments , Operators och Sequences läggs den länkade listan för vars Sequence man "är i".

När hela parsningen är klar så får man bara en Sequence tillbaka.
Efter det så kan man kalla på Sequence.getResult() vilket returnerar ett Argument (ett tal/resultat).

Evalueringen är en liten fuling.
Den letar igenom den länkade listan efter Operators och tar då den noden och exekverar på detta vis operator.eval(FÖRRA NODEN, NÄSTA NOD) vilket returnerar ett Argument. Detta Argument sätts till nuvarande noden och de tre övriga noderna (operator, argument1, argument2) tas bort från listan.

Blir många loopar då den utför operationerna i rätt ordning... parenteser, multiplikation etc etc. alltid från vänster till höger.

En optimering skulle kunna vara att beräkna varje Sequence direkt efter parsning. Jag ville ha det i två distinkta steg, speciellt så att man kan visuellt leka med uträkningarna medan och under beräkningen.

Dold text

Kod

public abstract class MathNode { } public abstract class Operator : MathNode { public static Dictionary<char, Operator> Hash = new Dictionary<char, Operator>() .Append('-', new SubOperator()) .Append('+', new AddOperator()) .Append('/', new DivOperator()) .Append('*', new MulOperator()) .Append('%', new RemOperator()) .Append('s', new SqrOperator()) .Append('^', new PowOperator()); public Argument evaluate(Argument arg1, Argument arg2) { return eval(arg1, arg2); } protected abstract Argument eval(Argument arg1, Argument arg2); } public class AddOperator : Operator { protected override Argument eval(Argument arg1, Argument arg2) { return new Argument(arg1.Value + arg2.Value); } } public class SubOperator : Operator { protected override Argument eval(Argument arg1, Argument arg2) { return new Argument(arg1.Value - arg2.Value); } } public class MulOperator : Operator { protected override Argument eval(Argument arg1, Argument arg2) { return new Argument(arg1.Value * arg2.Value); } } public class DivOperator : Operator { protected override Argument eval(Argument arg1, Argument arg2) { return new Argument(arg1.Value / arg2.Value); } } public class RemOperator : Operator { protected override Argument eval(Argument arg1, Argument arg2) { return new Argument(arg1.Value % arg2.Value); } } public class PowOperator : Operator { protected override Argument eval(Argument arg1, Argument arg2) { return new Argument(Math.Pow(arg1.Value, arg2.Value)); } } public class SqrOperator : Operator { protected override Argument eval(Argument arg1, Argument arg2) { return new Argument(Math.Sqrt(arg1.Value)); } } public class MathEvaluator { public static Argument eval(string text) { text = text.Replace(" ", ""); var sequence = parse(text); return sequence.getResult(); } // 5 + (2 * 3) + (s9 ^ 2) - 5(2 - (-1)) private static Sequence parse(string text) { var sequence = new Sequence(); var number = ""; for(int i = 0; i < text.Length; i++) { sequence.CharsProcessed++; var c = text[i]; if (char.IsNumber(c) || c == '.' || c == ',') { number += c; number = number.Replace('.', ','); continue; } else { if (number != "") { sequence.AddNode(new Argument(number)); number = ""; } } if (c == '(') { if (sequence.Nodes.Last != null && sequence.Nodes.Last.Value is Argument) { sequence.Nodes.AddLast(new MulOperator()); } var innerSequence = parse(text.Substring(i+1)); sequence.AddNode(innerSequence); i += innerSequence.CharsProcessed; sequence.CharsProcessed += innerSequence.CharsProcessed; continue; } if (c == ')') break; if (Operator.Hash.ContainsKey(c)) { var op = Operator.Hash[c]; if (sequence.Nodes.First == null && op is SubOperator) { sequence.AddNode(new Argument(0)); } sequence.AddNode(op); continue; } throw new Exception("Unrecognized character in eval '" + c+"'"); } if (number != "") { sequence.AddNode(new Argument(number)); number = ""; } return sequence; } } public class Sequence : MathNode { public LinkedList<MathNode> Nodes { get; set; } public LinkedListNode<MathNode> CurrentNode { get; set; } public int CharsProcessed { get; set; } public Sequence() { Nodes = new LinkedList<MathNode>(); } public void AddNode(MathNode node) { Nodes.AddLast(node); } public Argument getResult() { evalSequences(); evalSqr(); evalPow(); evalDivMulRem(); evalSubAdd(); if (Nodes.First.Next == null) { return Nodes.First.Value as Argument; } return getResult(); } private void evalPow() { CurrentNode = Nodes.First; do { if (CurrentNode.Value is PowOperator) { perform(); } CurrentNode = CurrentNode.Next; } while (CurrentNode != null); } private void perform() { var op = CurrentNode.Value as Operator; var firstArg = CurrentNode.Previous.Value as Argument; var secondArg = CurrentNode.Next.Value as Argument; var result = op.evaluate(firstArg, secondArg); Nodes.AddBefore(CurrentNode.Previous, result); var resultNode = CurrentNode.Previous.Previous; Nodes.Remove(CurrentNode.Next); Nodes.Remove(CurrentNode.Previous); Nodes.Remove(CurrentNode); CurrentNode = resultNode; } private void evalSqr() { CurrentNode = Nodes.First; do { if (CurrentNode.Value is SqrOperator) { var op = CurrentNode.Value as Operator; var secondArg = CurrentNode.Next.Value as Argument; var result = op.evaluate(secondArg, secondArg); Nodes.AddBefore(CurrentNode, result); var resultNode = CurrentNode.Previous; Nodes.Remove(CurrentNode.Next); Nodes.Remove(CurrentNode); CurrentNode = resultNode; } CurrentNode = CurrentNode.Next; } while (CurrentNode != null); } private void evalSubAdd() { CurrentNode = Nodes.First; do { if (CurrentNode.Value is SubOperator || CurrentNode.Value is AddOperator) { perform(); } CurrentNode = CurrentNode.Next; } while (CurrentNode != null); } private void evalDivMulRem() { CurrentNode = Nodes.First; do { if (CurrentNode.Value is MulOperator || CurrentNode.Value is DivOperator || CurrentNode.Value is RemOperator) { perform(); } CurrentNode = CurrentNode.Next; } while (CurrentNode != null); } private void evalSequences() { CurrentNode = Nodes.First; do { if (CurrentNode.Value is Sequence) { var arg = (CurrentNode.Value as Sequence).getResult(); Nodes.AddBefore(CurrentNode, arg); var argNode = CurrentNode.Previous; Nodes.Remove(CurrentNode); CurrentNode = argNode; } CurrentNode = CurrentNode.Next; } while (CurrentNode != null); } } public class Argument : MathNode { public double Value { get; set; } public Argument(double value) { Value = value; } public Argument(string value) { Value = Double.Parse(value); } public override string ToString() { return Value.ToString(); } } public static class Extensions { public static Dictionary<TKey, TValue> Append<TKey, TValue>(this Dictionary<TKey, TValue> dict, TKey key, TValue value) { dict[key] = value; return dict; } }

Dold text
Visa signatur

ηλί, ηλί, λαμά σαβαχθανί!?

Permalänk
Datavetare
Skrivet av Izlandi:

Var exakt detta jag var inne på med min referens till HP48 ovan som kör med "reverse polish notation" (RPN) a.k.a. post-fix. Är nog en av de enklaste sätten att lösa denna uppgift. Ska ta och svänga ihop en egen lösning med denna algoritm i Go

Tror du har ett litet typo i namngivningen av en av metoderna, ConvertToInfix ska nog heta ConvertToPostfix då input är Infix och man vill ha ut Postfix (RPN).

Gissar att de flesta miniräknare där man kan skriva in uttryck rak upp och ner med infix operatorer just använder sig av Dijkstra's shunting yard

Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Datavetare
Skrivet av Izlandi:

Väldigt snarlikt program i Go

calc_shunt_yard.go

package main import ( "bufio" "fmt" "os" "strconv" "strings" "text/scanner" ) type Op interface { Apply(a, b int) int Precedence() int } const NopRune = '?' type Nop struct {} type Mul struct {} type Div struct {} type Add struct {} type Sub struct {} func (op Nop) Apply(a, b int) int { panic("Tried call Apply on Nop") } func (op Add) Apply(a, b int) int { return a + b } func (op Sub) Apply(a, b int) int { return a - b } func (op Mul) Apply(a, b int) int { return a * b } func (op Div) Apply(a, b int) int { return a / b } func (op Nop) Precedence() int { return 0 } func (op Add) Precedence() int { return 1 } func (op Sub) Precedence() int { return 1 } func (op Mul) Precedence() int { return 2 } func (op Div) Precedence() int { return 2 } type Calc struct { numSt []int opSt []rune } type Token struct { what rune repr string } func (calc *Calc) Push(n int) { calc.numSt = append(calc.numSt, n) } func (calc *Calc) Pop() int { if len(calc.numSt) == 0 { return 0 } n := calc.numSt[len(calc.numSt) - 1] calc.numSt = calc.numSt[0:len(calc.numSt) - 1] return n } func (calc *Calc) PushOp(op rune) { if op != NopRune { calc.opSt = append(calc.opSt, op) } } func (calc *Calc) PopOp() rune { if len(calc.opSt) == 0 { return NopRune } op := calc.opSt[len(calc.opSt) - 1] calc.opSt = calc.opSt[0:len(calc.opSt) - 1] return op } func ToOp(opR rune) Op { switch opR { case '+': return Add{} case '-': return Sub{} case '*': return Mul{} case '/': return Div{} case NopRune: return Nop{} default: panic(fmt.Sprintf("Invalid operator: %v", opR)) } } /* * Applies an operator to the two top element on the number stack and * push the result back to the number stack */ func (calc *Calc) ApplyOp(op rune) { b := calc.Pop() a := calc.Pop() calc.Push(ToOp(op).Apply(a, b)) } /* * Implements shunting yard algorithm */ func (calc *Calc) DoToken(tok Token) { switch tok.what { case scanner.Int: n, _ := strconv.ParseInt(tok.repr, 0, 64) calc.Push(int(n)) case '(': calc.PushOp(tok.what) case ')': for { op := calc.PopOp() if op == '(' { break } calc.ApplyOp(op) } default: op := ToOp(tok.what) for { cop := calc.PopOp() if cop == '(' || op.Precedence() > ToOp(cop).Precedence() { calc.PushOp(cop) break } calc.ApplyOp(cop) } calc.PushOp(tok.what) } } /* * Turns the stream of token into integer and operators, push and * evaluate them to a number stack and operator stack according to the * shunting yard algorithm for turing infix into postfix operators. */ func Eval(tokens []Token) int { var calc Calc for _, tok := range(tokens) { calc.DoToken(tok) } for len(calc.opSt) > 0 { calc.ApplyOp(calc.PopOp()) } return calc.Pop() } /* * Turn an expression into tokens, * "1 + 2" -> {{scanner.Int,"1"},{'+',"+"},{scanner.Int,"2"}} */ func Tokenize(expr string) []Token { toks := []Token{} sc := &scanner.Scanner{Mode: scanner.ScanInts | scanner.ScanStrings} sc.Init(strings.NewReader(expr)) for t := sc.Scan(); t != scanner.EOF; t = sc.Scan() { toks = append(toks, Token{repr: sc.TokenText(), what: t}) } return toks } func main() { lineScanner := bufio.NewScanner(os.Stdin) for lineScanner.Scan() { fmt.Println("=", Eval(Tokenize(lineScanner.Text()))) } }

Dold text
Visa signatur

Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer

Permalänk
Medlem

Äntligen!

Efter många timmar av eget försök utan någon hjälp från google eller denna tråd försökte jag lösa uppgiften. Efter allt för stora problem med att tämja prioriterings reglerna googlade jag efter en infix parser. Hittade då wikipedia sidan om Järnvägsalgoritmen.

Med hjälp av den algoritmen så skrev jag om all min kod och löste uppgiften helt på egen hand och mycket mer elegant.

Är fett nöjd. Snygg kod och enkelt att lägga till nya operatorer. Just nu har jag lagt in ^ * / + -.
TODO: Decimaler och ev felhantering.

PHP, Järnvägsalgoritmen (shunting yard algorithm).

<?php /** * Alla funktioner min miniräknar stödjer. * * assoc = associative. -1 = vänster associativ. 0 = associativ. 1 = höger associativ. * * Notera att funktionerna tar f($b, $a) och inte f($a, $b). Detta pga RPN, stackbaserat. * Argumenten kommer i tvärtom ordning. */ $ops = ['^' => ['assoc' => 1, 'prio' => 3, 'function' => function($b, $a) { return pow($a, $b); }], '*' => ['assoc' => 0, 'prio' => 2, 'function' => function($b, $a) { return $a * $b; }], '/' => ['assoc' => 0, 'prio' => 2, 'function' => function($b, $a) { return $a / $b; }], '+' => ['assoc' => 0, 'prio' => 1, 'function' => function($b, $a) { return $a + $b; }], '-' => ['assoc' => 0, 'prio' => 1, 'function' => function($b, $a) { return $a - $b; }]]; /** * http://sv.wikipedia.org/wiki/J%C3%A4rnv%C3%A4gsalgoritmen */ function shunting_yard($xs) { global $ops; $stack = []; $out = []; $x = reset($xs); //Läs in alla tecken från streamen do { //Nummer? Pusha till utdatan if(is_numeric($x)) { //TODO: decimaltal $num = $x; $x = next($xs); // Är nästa $x också ett nummer? Då hade vi ett nummer större än 9 här. // Tex 937. while(is_numeric($x)) { $num .= $x; $x = next($xs); } prev($xs); $num = intval($num); array_push($out, $num); } //Operator? elseif(in_array($x, array_keys($ops), true)) { //Finns det någon operator i stacken? if(count($stack) AND in_array(end($stack), array_keys($ops), true)) { // Har $x lägre eller samma prioritet som sista operatorn på stacken? // OCH är $x vänster associativ / associativ. if( ($ops[$x]['prio'] <= $ops[end($stack)]['prio'] AND $ops[$x]['assoc'] < 1) // ELLER // Är $x höger associativ (tex ^) OCH har $x lägre prio än operatorn på stacken? OR ($ops[$x]['assoc'] === 1 AND $ops[$x]['prio'] < $ops[end($stack)]['prio'])) { array_push($out, array_pop($stack)); } } array_push($stack, $x); } elseif($x == '(') { array_push($stack, $x); } // elseif($x == ')') { while( ($y = array_pop($stack)) != '(' ) array_push($out, $y); } } while( ($x = next($xs)) !== false); //Finns det kvar operatorer på stacken? Lägg till dem i utdatan. while(count($stack) > 0) array_push($out, array_pop($stack)); return $out; } function evalulate_rpn($rpn) { global $ops; $stack = []; foreach ($rpn as $x) { //Nummer? Pusha till utdatan if(is_numeric($x)) { array_push($stack, $x); } else { //Kör min egna version av operatorn (beräkningarna sker här) $result = $ops[$x]['function'](array_pop($stack), array_pop($stack)); array_push($stack, $result); } } return $stack[0]; } $input = str_split($argv[1]); //Input $rpn = shunting_yard($input); //Infix -> rpn $result = evalulate_rpn($rpn); //Räkna ut resultatet echo $result; ?>

Dold text
Visa signatur

Programmerare -> PHP | HTML | CSS | JS | Java.