Einen mathematischen Ausdruck in einer Zeichenkettenform auswerten

Question

Dies ist eine Standardinterviewfrage, die einen mathematischen Ausdruck in Form einer Zeichenkette auswertet.

zur Verfügung gestellt, also '3+3-6*2' Die Antwort sollte -6

Nun, wenn die Ausdrücke unterstützt nur vier Operationen +,-,*,/ Dann gibt es eine einfache Möglichkeit, es mit einem Stapel zu tun.

Ich habe es gelöst, indem ich die Infix-Notation in Postfix umgewandelt und dann mit einem Stack gelöst habe - aber ich suche nach einem anderen Ansatz, der nur diese vier Operationen unterstützt. Dies ist meine Lösung,

def evaluate(self, s: str) -> int: 
    expr = [i for i in re.split(r'(\d+|\W+)', s) if i] 
    rpn = self.convertToPostfix(expr) 
    return self.evalPostfix(rpn) 

def convertToPostfix(self, infix: list) -> list: 
    stack = collections.deque() 
    result = [] 
    for item in infix: 
     if item.isdigit(): 
      result.append(item) 
     else: 
      while len(stack) > 0 and self.has_higher_precedence(stack[-1], item): 
       result.append(stack[-1]) 
       stack.pop() 
      stack.append(item) 
    while len(stack) > 0: 
     result.append(stack.pop()) 
    return result 

def has_higher_precedence(self, a: str, b: str) -> bool: 
    if a == '/' and b == '*' or b == '+' or b == '-': 
     return True 
    if a == '*' and b == '+' or '-': 
     return True 
    if a == '+' and b == '-': 
     return True 
    return False 

def evalPostfix(self, p: list) -> int: 
    stack = collections.deque() 
    for item in p: 
     if item.isdigit(): 
      stack.append(int(item)) 
     elif item[1:].isdigit(): 
      stack.append(int(item)) 
     else: 
      curr = stack.pop() 
      prev = stack.pop() 
      if item == '+': 
       total = prev + curr 
      elif item == '-': 
       total = prev - curr 
      elif item == '*': 
       total = prev * curr 
      else: 
       total = prev/curr 
      stack.append(total) 
    return stack.pop() 

auch bewusst, dass ich bin, dass dies durch die Entwicklung eines rekursiven lexikalischen Parser gelöst werden kann, aber das ist über den Rahmen dieser Frage.

Also meine Frage ist, gibt es eine einfache Möglichkeit, dies in O (n) Zeit mit einem Stapel zu tun, wenn es nur vier Betreiber

Answer 1

Sie können den Algorithmus des Rangierbahnhofs so ändern, dass er in einem einzigen Durchgang analysiert und ausgewertet wird. Der Zwischenschritt der Konvertierung in Postfix entfällt. Die Beschränkung des Problems auf nur die vier mathematischen Standardoperatoren ohne Klammern ändert den grundlegenden Ansatz nicht.

Hier ist der Standard-Shunting-Yard-Algorithmus, aus dem verknüpften Artikel. Ich habe unten als Referenz Zeilennummern hinzugefügt:

1: while there are tokens to be read: 
2: read a token. 
3: if the token is a number, then push it to the output queue. 
4: if the token is an operator, then: 
5:  while (there is an operator at the top of the operator stack with 
6:   greater precedence) or (the operator at the top of the operator stack has 
7:      equal precedence and 
8:      the operator is left associative) and 
9:      (the operator at the top of the stack is not a left bracket): 
10:    pop operators from the operator stack, onto the output queue. 
11:  push the read operator onto the operator stack. 
12: if the token is a left bracket (i.e. "("), then: 
13:  push it onto the operator stack. 
14: if the token is a right bracket (i.e. ")"), then: 
15:  while the operator at the top of the operator stack is not a left bracket: 
16:   pop operators from the operator stack onto the output queue. 
17:  pop the left bracket from the stack. 
     /* if the stack runs out without finding a left bracket, then there are 
18:  mismatched parentheses. */ 
19: if there are no more tokens to read: 
20:  while there are still operator tokens on the stack: 
21:   /* if the operator token on the top of the stack is a bracket, then 
22:   there are mismatched parentheses. */ 
23:   pop the operator onto the output queue. 
24: exit. 

Die Modifikationen beinhalten die Ausgabewarteschlangen mit einem Operandenstapel ersetzt: ein Stapel von ganzen Zahlen. Wenn Sie beispielsweise in Zeile 3 die Nummer nicht in die Ausgabewarteschlange schieben, drücken Sie die Nummer auf den Operandenstapel. Dies erfordert natürlich, dass Sie das Zeichen in eine Ganzzahl konvertieren.

Dann auf der Linie 10, wo Sie Pop-Betreiber aus dem Operator-Stack und drückt, um die Ausgabewarteschlange, Sie stattdessen:

1. einen Operator Pop
2. Pop zwei Operanden aus dem Operandenstapel
3. Perform der Betrieb
4. das Ergebnis wieder auf den Operandenstapel schieben

Sie Linien ersetzen 16 und 23 mit dem gleiche Art von Logik.

Wenn Sie zu irgendeinem Zeitpunkt beim Auswerten nicht genügend Operanden auf dem Operandenstapel haben, dann haben Sie nicht übereinstimmende Operatoren: etwas wie 2 + 3 + - (außer Sie entscheiden sich für unäre + und unäre -), oder 2 */3.

Wenn Sie Zeile 24 erreicht haben, ist der Operatorstapel leer und der Operandenstapel sollte einen einzelnen Wert enthalten: das Endergebnis. Wenn mehr als ein Element auf dem Operandenstapel ist, dann haben Sie zu viele Operanden (sollte nicht passieren).

Ersetzen Sie also die Zeile 24 durch einen Popup aus dem Operandenstapel, und Sie können das als Ergebnis zurückgeben.

Der Shunting-Yard ist eigentlich eine sehr vereinfachte Version des "rekursiven lexikalischen Parsers", die Sie erwähnt haben. Anstatt Stack-Frames durch Rekursion zu erstellen, werden die Stacks direkt manipuliert.

Das Ändern Ihres Codes sollte nicht zu schwierig sein. Unten ist eine modifizierte Version Ihrer convertToPostfix-Funktion, genannt evaluateInfix, die alles in einem einzigen Durchlauf erledigt. Beachten Sie, dass ich nicht ein Python-Programmierer bin, so werde ich den Code nicht garantieren einwandfrei funktionieren, aber es sollte Ihnen die Idee geben:

def evaluateInfix(self, infix: list) -> int: 
    operatorStack = collections.deque() 
    operandStack = collections.deque() 
    result = [] 
    for item in infix: 
     if item.isdigit(): 
      val = convertDigitToNumber(item) // however that's done 
      // push to operand stack 
      operandStack.append(val) 
     else: 
      while len(operatorStack) > 0 and self.has_higher_precedence(operatorStack[-1], item): 
       // pop two operands from stack, evaluate, and push result 
       // call this "pop and eval" 
       op2 = operandStack[-1] 
       operandStack.pop() 
       op1 = operandStack[-1] 
       operandStack.pop() 
       operator = operatorStack[-1] 
       operatorStack.pop() 
       val = evaluate(operator, op1, op2) // this function evaluates op1 <operator> op2 

       // push result back onto operand stack 
       operandStack.append(val) 
      operatorStack.append(item) 
    while len(operatorStack) > 0: 
     // insert "pop and eval" code here 
    // at this point there should be a single value on the operand stack 
    return operandStack[-1] 

Die evaluate Funktion einen Operator und zwei Operanden macht, macht sie den Betrieb und gibt das Ergebnis zurück. So gegeben ('+', 3, 5), würde es 3+5 berechnen und 8 zurückgeben.

Die Idee hier ist, dass, wenn Sie auswerten, Sie zwei Operanden und einen einzigen Operator nehmen.

Testfall: 3+5*2.

 operand operator 
char stack  stack 
-------------------------- 
    3  [3]  [] 
    +  [3]  [+] 
    5  [3,5]  [+] 
    *  [3,5]  [+,*] 
    2  [3,5,2] [+,*] 
<end> 
at this point, we're at the end of the string. 
Pop 2 and 5 from the operand stack, pop * from the operator stack, 
and evaluate 
     [3,10] [+] 
pop and eval again 
     [13]  [] 
operator stack is empty. Pop result from operand stack and return. 

Answer 2

Sie die Zeichenfolge als eine Liste von Zeichen speichern kann und dann durchlaufen Sie es 2-mal linear, wobei Sie zuerst für die Multiplikation/Division und dann für die Addition/Subtraktion berechnen.

das heißt in der ersten Iteration haben

1+10/2 -> 1 + 5 

dann

leicht mit einem Stapel implementiert werden, auf die man die Zahlen mit dem + Dies könnte

1 + 5 -> 6 

haben auch oder fügen Sie - Zeichen. Wenn Sie dem Stack hinzufügen und feststellen, dass Sie ein / oder * Zeichen erreicht haben, blenden Sie das vorherige Element ein, multiplizieren oder dividieren Sie es mit der aktuellen Nummer und drücken es zurück. Schließlich finden Sie die Summe aller Elemente in einem Stapel.

Noch weiter können Sie die Beobachtung machen, dass im vorherigen Beispiel das einzige Element des verwendeten Stapels direkt vor der Antwort verwendet wurde. Dies deutet darauf hin, dass Sie das vorherige Element speichern können, während Sie eine Summe beibehalten, und wenn Sie ein * oder / Zeichen erreichen, subtrahieren Sie dann das vorherige Element von der Summe und fügen Sie das aktualisierte Element hinzu. Diese Methode löst das Problem effektiv in einem O (n) -Scan mit O (1) Extra-Speicher und ist damit möglicherweise die optimale Lösung für dieses Problem.

Answer 3

Zur Vervollständigung halber veröffentlichen @ Jim Mischel Lösung als Python 3-Code arbeiten.

import re 


class Solution: 
    def evalExpression(self, s): 
     operator_stack, operand_stack = [], [] 
     tokens = [i for i in re.split(r'(\d+|\W+)', s) if i] 
     for token in tokens: 
      if token.isdigit(): 
       operand_stack.append(int(token)) 
      else: 
       while len(operator_stack) > 0 and self.has_higher_precedence(operator_stack[-1], token): 
        val = self.evaluate(operand_stack.pop(), operator_stack.pop(), operand_stack.pop()) 
        operand_stack.append(val) 
       operator_stack.append(token) 
     while len(operator_stack) > 0: 
      val = self.evaluate(operand_stack.pop(), operator_stack.pop(), operand_stack.pop()) 
      operand_stack.append(val) 
     return operand_stack[-1] 

    def has_higher_precedence(self, opr1, opr2): 
     if opr1 == '/' or opr1 == '*' and opr2 == '+' or opr2 == '-': 
      return True 
     return False 

    def evaluate(self, a, b, c): 
     if b == '/': 
      return c/a 
     elif b == '*': 
      return c*a 
     elif b == '-': 
      return c-a 
     else: 
      return c+a 


if __name__ == '__main__': 
    solution = Solution() 
    print(solution.evalExpression('3+3-6*2'))