Rekursive Funktion

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Qubit
User
Beiträge: 128
Registriert: Dienstag 7. Oktober 2008, 09:07

Oder mit mehrstelligen ganzen Zahlen:

Code: Alles auswählen

def calc(parse_string):
  result = 0

  if not parse_string.isnumeric():

    if "*" in parse_string:
      mul1, mul2 = parse_string.split("*", 1)
      result = calc(mul1) * calc(mul2)

    if "+" in parse_string:
      add1, add2 = parse_string.split("+", 1)
      result = calc(add1) + calc(add2)

  else:
    result = int(parse_string)
  return result

if __name__ == '__main__':

  TERM = '3+4*5+6+1*13'
  print(f"{TERM} = { calc(TERM) }")
Qubit
User
Beiträge: 128
Registriert: Dienstag 7. Oktober 2008, 09:07

Sirius3 hat geschrieben: Samstag 25. Juni 2022, 15:13 Eingerückt wird immer mit 4 Leerzeichen pro Ebene, zwei sind zu wenig.
Das result = 0 am Anfang wird nie benutzt, kann also weg.
Es ist sehr undurchsichtig, dass erst der Term an * gesplittet wird, und daraus ein Ergebnis berechnet wird, dann aber, falls doch noch ein + im Term ist, dieses (falsche) Ergebnis verworfen wird und das richtige berechnet wird.
Warum nennst Du unten den Term zwar `TERM`, in der Funktion das Argument dann `parse_string`?
result=0 zeigt gleich den Rückgabetyp, auch wenn er in Python überflüssig ist. Ebenso zeigt "parse_string" den Parametertyp.
Deine Bemerkung zur Funktionalität verstehe ich nicht. Was meinst du mit "verworfen"?
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

Der Typ hat im Namen der Variable nichts verloren. Und auch unsinnigen Code zu haben, nur dass ein Leser weiß, welchen Typ die Rückgabe hat, hab ich auch noch nie gesehen.
Der Nutzer weiß, um welche Typen es sich handelt, sieht er, wenn er die Dokumentation liest:

Code: Alles auswählen

def calc(term):
    """ calculates the result of the term.

    Arguments:
        term: a string with single digites
            combined with the operators + or *

    Returns:
        the result as integer
    """
    if not term.isnumeric():
        if "*" in term:
            subterm1, subterm2 = term.split("*", 1)
            result = calc(subterm1) * calc(subterm2)

        if "+" in parse_string:
            subterm1, subterm2 = parse_string.split("+", 1)
            result = calc(subterm1) + calc(subterm2)
    else:
        result = int(term)
    return result
Und dann gib mal aus, welche Teil-Terme alle berechnet werden, und was das Ergebnis davon ist.
nezzcarth
User
Beiträge: 1632
Registriert: Samstag 16. April 2011, 12:47

@Qubit: Deine Lösung liefert korrekte Ergebnisse und reicht zum Berechnen der vorgegebenen Eingabe aus. Ich habe aber bei einem etwas hemdsärmligen Test den Eindruck gewonnen, dass sie im Vergleich zu einer stärker rekursiven Lösung nicht sehr performant ist. Insb. bei Eingaben ab ca. 30 Elementen:

Code: Alles auswählen

In [3]: from random import choices

In [4]: from time import time

In [5]: def random_expression(length):
   ...:     if length <2:
   ...:         raise ValueError
   ...:     numbers = list(map(str, choices(range(1,10), k=length)))
   ...:     operations = choices(('+', '*'), k=length-1)
   ...:     expression = [numbers[0]] + [element for item in zip(operations, numbers) for element in item]
   ...:     return ''.join(expression)
   ...: 

In [6]: start = time()
   ...: for i in range(2, 40):
   ...:     for _ in range(10):
   ...:         expression = random_expression(i)
   ...:         assert eval(expression) == calc_qubit(expression)
   ...: print(time()-start)

173.55928134918213

In [7]: start = time()
   ...: for i in range(2, 40):
   ...:     for _ in range(10):
   ...:         expression = random_expression(i)
   ...:         assert eval(expression) == calc2(expression)
   ...: print(time()-start)
0.02144646644592285
("calc2" ist eine stärker rekursive Variante; das nur mal als grober Eindruck, wenn man es vergleichbarer möchte, sollte man natürlich mit denselben Eingaben testen und vielleicht auch die Berechnung des Vergleichsergebnisses vorab erledigen. Bevorzugt ohne eval :))

Ich denke, das liegt daran, dass die Rekursion bei dir evtl. nicht optimal umgesetzt ist. Du merkst dir Zwischenwerte, statt direkt mit return zu arbeiten. Zudem könnte man die Reihenfolge der Bedingungen umdrehen.
Zuletzt geändert von nezzcarth am Samstag 25. Juni 2022, 16:07, insgesamt 3-mal geändert.
Qubit
User
Beiträge: 128
Registriert: Dienstag 7. Oktober 2008, 09:07

Sirius3 hat geschrieben: Samstag 25. Juni 2022, 15:38 Und dann gib mal aus, welche Teil-Terme alle berechnet werden, und was das Ergebnis davon ist.
Ah, danke, da hast du Recht.
Jetzt sollten die Rekursionen mit der Anzahl der Operationen übereinstimmen:

Code: Alles auswählen

def calc(term):
  match = False

  if not term.isnumeric():

    if not match and "+" in term:
      match = True
      add1, add2 = term.split("+", 1)
      result = calc(add1) + calc(add2)

    if not match and "*" in term:
      match = True
      mul1, mul2 = term.split("*", 1)
      result = calc(mul1) * calc(mul2)

  else:
    result = int(term)

  return result

if __name__ == '__main__':

  TERM = '3+4*5+6+1*13'
  print(f"{TERM} = { calc(TERM) }")
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Ich fand das auch verwirrend weil ich beim ersten Lesen sofort gedacht hatte, hey das wird in der falschen Reihenfolge berechnet, man muss doch "+" *vor* "*" behandeln.

Man könnte auch einfach den „single exit point“ fallen lassen, dann würde `result` mit 0 initialisieren noch weniger Sinn machen, weil es dann gar kein `result` gibt:

Code: Alles auswählen

def calc(term):
    if "+" in term:
        subterm1, subterm2 = term.split("+", 1)
        return calc(subterm1) + calc(subterm2)

    if "*" in term:
        subterm1, subterm2 = term.split("*", 1)
        return calc(subterm1) * calc(subterm2)

    return int(term)
Meine Lösung sieht so aus:

Code: Alles auswählen

#!/usr/bin/env python3
from operator import add, mul as multiply


def evaluate(expression):
    for operator, function in [("+", add), ("*", multiply)]:
        left, found_operator, right = expression.partition(operator)
        if found_operator == operator:
            return function(evaluate(left), evaluate(right))

    return int(expression, 0)


def main():
    print(evaluate("3+4*5+6+1*3"))
    print(evaluate("4711 + 42 * 23"))
    print(evaluate("0b0001_0110 + 0xDeadBeef * 1_000_000"))


if __name__ == "__main__":
    main()
Basiert auf dem Vorgänger von dem folgenden Pascal-Programm. Vorgänger, weil diese Version nicht mehr Zeichenketten durch die Gegend kopiert, sondern mit `TStr` eine Art ”View” in die *eine* Zeichenkette ermöglicht, und damit bei jedem Aufteilen nur konstant viel Daten belegt werden, egal wie lang der Ausdruck ist.

Code: Alles auswählen

program Eval;

type
  TOpFunc = function(a, b: Integer) : Integer;
  TOperation = record
    symbol: Char;
    func: TOpFunc;
  end;
  TStr = record
    str: ^String;
    start, end_: Byte;
  end;
  TTestCase = record
    expression: String;
    expected: Integer;
  end;


function Add(a, b: Integer) : Integer;
begin
  Add := a + b;
end;

function Multiply(a, b: Integer) : Integer;
begin
  Multiply := a * b;
end;


const
  Operations: array[0..1] of TOperation = (
      (symbol: '+'; func: Add),
      (symbol: '*'; func: Multiply));

  TestCases: array[0..4] of TTestCase = (
      (expression: '1'; expected: 1),
      (expression: '2+3'; expected: 5),
      (expression: '3*4'; expected: 12),
      (expression: '3+4*5+6+1*3'; expected: 32),
      (expression: '4711+42*23'; expected: 5677));


procedure InitStr(var str: TStr; const s: String);
begin
  str.str := @s;
  str.start := 1;
  str.end_ := Length(s);
end;

function SplitStrAt(const str: TStr; c: Char; var left, right: TStr) : Boolean;
var
  i: Byte;
begin
  for i := str.start to str.end_ do
    if str.str^[i] = c then
      begin
        left.str := str.str;
        left.start := str.start;
        left.end_ := i - 1;

        right.str := str.str;
        right.start := i + 1;
        right.end_ := str.end_;

        SplitStrAt := true;
        Exit;
      end;

  SplitStrAt := false;
end;

function StrAsNumber(const str: TStr; var result: Integer) : Boolean;
var
  i: Byte;
  digit: Integer;
begin
  result := 0;
  for i := str.start to str.end_ do
    begin
      digit := Ord(str.str^[i]) - Ord('0');
      if (digit < 0) or (digit > 9) then
        begin
          StrAsNumber := false;
          Exit;
        end;

      result := result * 10 + digit;
    end;

  StrAsNumber := true;
end;


function Evaluate(const expr: TStr) : Integer;
var
  i: Byte;
  left, right: TStr;
  result: Integer;
begin
  for i := Low(Operations) to High(Operations) do
    with Operations[i] do
      begin
        if SplitStrAt(expr, symbol, left, right) then
          begin
            Evaluate := func(Evaluate(left), Evaluate(right));
            Exit;
          end;
      end;

  if not StrAsNumber(expr, result) then
    begin
      WriteLn('Error in parsing "', expr.str^, '" as a number.');
      Halt;
    end;

  Evaluate := result;
end;


procedure Tests;
var
  i, result: Integer;
  expr: TStr;
begin
  for i := Low(TestCases) to High(TestCases) do
    with TestCases[i] do
      begin
        InitStr(expr, expression);
        result := Evaluate(expr);

        Write(expression, ' = ', result, ' ');
        if result = expected then
          WriteLn(' Ok')
        else
          WriteLn('<> ', expected);
      end;
end;


begin
  Tests;
end.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@Qubit: `match` macht keinen Sinn. Es gibt ``elif``/``else`` für so etwas. Und wie gesagt, das geht deutlich einfacher wenn man nicht darauf besteht das `result` überhaupt existieren muss.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Qubit
User
Beiträge: 128
Registriert: Dienstag 7. Oktober 2008, 09:07

__blackjack__ hat geschrieben: Samstag 25. Juni 2022, 16:15 @Qubit: `match` macht keinen Sinn. Es gibt ``elif``/``else`` für so etwas. Und wie gesagt, das geht deutlich einfacher wenn man nicht darauf besteht das `result` überhaupt existieren muss.
Ja, danke, macht Sinn.


Meine letzte Fassung für heute :)

Code: Alles auswählen

def calc(term):

  if term.isnumeric():
      return int(term)

  elif "+" in term:
      add1, add2 = term.split("+", 1)
      return calc(add1) + calc(add2)

  elif "*" in term:
      mul1, mul2 = term.split("*", 1)
      return calc(mul1) * calc(mul2)

if __name__ == '__main__':

    TERM = '3+4*5+6+1*13'
    print(f"{TERM} = { calc(TERM) }"
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

Ohne Rekursion läßt sich das auch recht kurz berechnen:

Code: Alles auswählen

def calc(term):
    result = 0
    current_product = 1
    for char in term:
        if char.isnumeric():
            current_product *= int(char)
        elif char == '+':
            result += current_product
            current_product = 1
    return result + current_product
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Okay, einen hätte ich noch. 8086-Assembler. Überstzen mit NASM; laufen lassen unter DOS:

Code: Alles auswählen

    cpu 8086
    org 100h

expr_length equ 80h
expr        equ 81h


segment .text
start:
    cld
    mov     al, [expr_length]
    or      al, al
    jz      print_usage
    
    mov     si, expr+1  ; +1 to skip the leading space DOS puts there.
    call    evaluate
    ;
    ; Print the result in AX as decimal number.
    ;
    xor     cx, cx      ; CX to count the decimal digits pushed to the stack.
    mov     bx, 10      ; Base 10.
.loop_1:
    xor     dx, dx      ; AX := AX/DX DIV 10; DX := AX/DX MOD 10
    div     bx
    or      dl, '0'     ; Push remainder as ASCII digit to the stack.
    push    dx
    inc     cx          ; Increase digit counter.
    
    or      ax, ax      ; Are we done?
    jnz      .loop_1

    mov     ah, 2       ; Print CX digits from stack.
.loop_2:
    pop     dx
    int     21h
    loop    .loop_2
    
    mov     ah, 9       ; Newline.
    mov     dx, crlf
    int     21h

end:
    ret

segment .rodata
usage_txt:
    db "Please give an expression with '+' and '*' and the numbers"
    db " 1,2,3,4,5,6,7,8,9", 13, 10
    db "without any spaces as command line argument.", 13, 10, '$'
segment .text

;--------------------------------------
print_usage:
    mov     ah, 9
    mov     dx, usage_txt
    int     21h
    ret

;--------------------------------------
; 
; n is on top of the stack.
;
; In:
;   SI = pointer to 0dh terminated expression string.
; Out:
;   AX = result
;--------------------------------------
evaluate:
    call    get_number      ; n := get_number()
    push    bp
    push    ax
    mov     bp, sp

.loop:
    mov     al, [si]        ; AL := operator.
    cmp     al, 0dh
    je      .no_operator
    inc     si
    
    cmp     al, '+'
    jne      .not_plus
    
    call    evaluate        ; n := n + evaluate()
    add     [bp], ax
    jmp     .loop
    
.not_plus:
    cmp     al, '*'
    jne     unexpected_operator
    
    call    get_number      ; n := n * get_number()
    mul     word [bp]
    mov     [bp], ax
    jmp     .loop
    
.no_operator:               ; AX := n
    pop     ax
    pop     bp
    ret

;--------------------------------------
; In:
;   SI = pointer to next character in expression.
; Out:
;   SI = pointer after the number in the expression.
;   AX = number
;--------------------------------------
get_number:
    xor     ah, ah
    lodsb
    cmp     al, 0dh
    je      unexpected_end

    sub     al, '0'
    jz      unexpected_digit
    cmp     ax, 9
    jg      unexpected_digit
    
    ret

;--------------------------------------
segment .rodata

unexpected_end_txt:
    db "unexpected end", 13, 10, '$'
unexpected_digit_txt:
    db "expected digit", 13, 10, '$'
unexpected_operator_txt:
    db "expected operator", 13, 10, '$'

caret:
    db '^'
crlf:
    db 13, 10, '$'

;--------------------------------------
segment .text

unexpected_end:
    mov     ax, unexpected_end_txt
    jmp     print_error
    
unexpected_digit:
    mov     ax, unexpected_digit_txt
    jmp     print_error
    
unexpected_operator:
    mov     ax, unexpected_operator_txt
    ; fallthrough

;--------------------------------------
; In:
;   AX := Pointer to $-terminated error message.
;--------------------------------------
print_error:
    push    ax
    
    mov     bl, [expr_length]   ; Put 0ah+'$' at the end of the expression
    xor     bh, bh              ; and then print it.
    mov     word [expr+1+bx], 240ah
    mov     ah, 9
    mov     dx, expr
    int     21h

    mov     cx, si      ; CX := index of the error in the expression - 1.
    sub     cx, expr+1
    
    mov     dl, ' '     ; Print spaces.
    mov     ah, 2
.loop:
    int     21h
    loop    .loop
    
    mov     dx, caret   ; Print '^' at place of the error.
    mov     ah, 9
    int     21h
    
    pop     dx          ; Print error message.
    mov     ah, 9    
    int     21h

    mov     ax, 4c01h   ; Halt the program with return code 1.
    int     21h
Testlauf mit allen drei möglichen Fehlerfällen:

Code: Alles auswählen

C:\>dir eval

 Volume in drive C is BROKEN
 Volume Serial Number is DEAD-CAFE
 Directory of C:\

EVAL     COM                363 30-06-2022 11:19a
    1 File(s)               363 Bytes
    0 Dir(s)         84,881,920 Bytes free

C:\>eval
Please give an expression with '+' and '*' and the numbers 1,2,3,4,5,6,7,8,9
without any spaces as command line argument.

C:\>eval hallo
 hallo
 ^
expected digit

C:\>eval 1
1

C:\>eval 1+
 1+
   ^
unexpected end

C:\>eval 1+2
3

C:\>eval 1+2*3
7

C:\>eval 42
 42
  ^
expected operator
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Antworten