Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer
Progblemet #10 - miniräknare
Senast redigerat
Visa signatur
Hur bulletproof ska koden vara? Räcker den med att den tar exakt den inputen du har skrivit?
Citera flera
Citera
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
Citera flera
Citera
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
Senast redigerat
Visa signatur
Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer
Citera flera
Citera
(1)
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
Citera flera
Citera
(2)
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.
Citera flera
Citera
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.
Senast redigerat
Visa signatur
Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer
Citera flera
Citera
Vet inte om jag missförstod uppgiften men såhär gjorde jag i python:
while True:
question = input()
print("=%d" % eval(question))
Citera flera
Citera
(4)
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å
Citera flera
Citera
(1)
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
Senast redigerat
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
Citera flera
Citera
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.
Citera flera
Citera
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
Senast redigerat
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.
Citera flera
Citera
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
Citera flera
Citera
(1)
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
Citera flera
Citera
En bra genomgång av detta för C++ finns i Stroustrups The C++ Programming Language, 4th ed. kapitel 10.
Visa signatur
.<
Citera flera
Citera
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.
Citera flera
Citera
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
Citera flera
Citera
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;
}
Citera flera
Citera
(2)
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
Senast redigerat
Visa signatur
.<
Citera flera
Citera
(1)
[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.
Citera flera
Citera
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.
Senast redigerat
Visa signatur
Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer
Citera flera
Citera
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
ηλί, ηλί, λαμά σαβαχθανί!?
Citera flera
Citera
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
Citera flera
Citera
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
Citera flera
Citera
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
Citera flera
Citera
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
Citera flera
Citera
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
ηλί, ηλί, λαμά σαβαχθανί!?
Citera flera
Citera
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
Citera flera
Citera
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
Citera flera
Citera
Ä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
Senast redigerat
Visa signatur
Programmerare -> PHP | HTML | CSS | JS | Java.
Citera flera
Citera
Hårdvara
- Igår Nytt vetenskapligt genombrott kan lösa OLED-inbränning 40
- Igår Microsoft vill göra handhållen Xbox 41
- 26 / 3 Microsoft patenterar teknik för bättre ray tracing-prestanda 27
- 26 / 3 Intel Battlemage med ordentlig prestandaökning dyker upp i databas 21
- 25 / 3 Gömda strömkontakter med Asus och Corsair 33
Mjukvara
- Idag Så byter du till gamla Notepad i Windows 11 14
- Idag Microsoft Copilot kan snart köras direkt på datorn 11
- Igår Stort steg för Windows på ARM: Google släpper optimerat Chrome 23
- Igår Xbox-chef är öppen för fler spelbutiker på konsol 21
- Igår DirectSR – så fungerar Windows inbyggda uppskalning för spel 15
Övrigt
- Igår Veckans fråga: Hur gammalt är ditt Steam-konto? 150
- Igår Bluffkampanj sprider sig genom Googles AI-sökfunktion 11
- 26 / 3 82 studenter avstängda för AI-fusk – Uppsala strängast 55
- 26 / 3 Speldistributörer kan lämna Xbox: "Döende i Europa" 101
- 26 / 3 Datorbyggarguide: Hur man installerar en processor i AMD:s sockel AM5 4
Datorkomponenter
Ljud, bild och kommunikation
- Hur investerar ni?10898
- Studera mjukvaruutvecklare till hösten3
- Microsoft Copilot kan snart köras direkt på datorn12
- Fråga om finansiering av husrenovering4
- söker rymd byggar spel18
- Så byter du till gamla Notepad i Windows 1114
- Köper från Aliexpress68
- Kassettdäck Nakamichi BX150-E problem3
- Speldator ca 15k 1440p inklusive 27" skärm14
- Zyxel U-1496E0
- Säljes Nvidia RTX 4090 FE
- Säljes PowerColor Radeon 7900 XTX Hellhound 24GB - Garanti
- Säljes ITX paket X570/5600
- Köpes Snabb "FPS-skärm"
- Skänkes StarTech | SV231DD2DUA | 2 Port Dual DVI USB KVM Switch with Audio & USB 2.0 Hub
- Säljes Pixel 7 Pro 128GB
- Säljes Atlantis Mini 4k, X2H Mini, GPX
- Säljes Hyperdrive SLAB 7-in-1 USB-C Hub
- Köpes AM4 Moderkort till 5600x sökes.
- Säljes BenQ XL2411 - 144 Hz
- Så byter du till gamla Notepad i Windows 1114
- Microsoft Copilot kan snart köras direkt på datorn12
- Stort steg för Windows på ARM: Google släpper optimerat Chrome23
- Nytt vetenskapligt genombrott kan lösa OLED-inbränning40
- Xbox-chef är öppen för fler spelbutiker på konsol21
- Veckans fråga: Hur gammalt är ditt Steam-konto?150
- Bluffkampanj sprider sig genom Googles AI-sökfunktion11
- DirectSR – så fungerar Windows inbyggda uppskalning för spel15
- Microsoft vill göra handhållen Xbox41
- 82 studenter avstängda för AI-fusk – Uppsala strängast55
Externa nyheter
Spelnyheter från FZ
- Hellgate gör comeback! Hellgate: Redemption har utannonserats idag
- Embracer säljer Gearbox till Take-Two för 4,9 miljarder idag
- Playstation utökar Game Help-funktionen med community-skapad vägledning idag
- Påstådda bilder på en vit Xbox Series X utan skivläsare har dykt upp idag
- No Man's Sky låter dig bygga om dina rymdskepp igår