数式を文字列形式で評価する

Question

これは標準的なインタビュー質問です。文字列の形式で与えられた数式を評価します。

に設けられ、'3+3-6*2' 答えは-6

式は4つだけの操作+,-,*,/ をサポートしている場合さて、スタックを使用してそれを行うための簡単な方法があるはずです。

私は中置記法を後置に変換し、それをスタックを使って解決することで解決しましたが、私はこれらの4つの操作だけをサポートする別のアプローチを探しています。これが私の解決策である、

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() 

はまた、私は、これは再帰的な字句パーサを設計することによって解決することができることを承知しているが、それはこの質問の範囲を超えています。スタックを使用して

だから私の質問は、Oでこれを行うための簡単な方法（n）の時間がある時のみ4事業者

Answer 1

Shunting-yardアルゴリズムを変更して、シングルパスでパーズして評価することができます。後置に変換する中間段階は必要ありません。括弧のない4つの標準的な算術演算子にのみ問題を限定しても、基本的なアプローチは変更されません。

リンクされた記事の標準Shunting-yardアルゴリズムは次のとおりです。私は以下の参照のために行番号を追加しました：

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. 

出力キューをオペランドスタック：整数のスタックで置き換えます。たとえば、出力キューに番号をプッシュするのではなく、3行目で番号をオペランドスタックにプッシュします。これはもちろん、文字を整数に変換する必要があります。

その後、あなたはオペレータスタックからオペレータをポップし、出力キューにプッシュライン10に、あなたの代わりに：

1. は、オペランドスタック
2. から2つのオペランドが実行オペレータ
3. ポップポップあなたがライン16と23を交換

操作 は、オペランドスタックに戻って結果をプッシュ

同じ種類の論理。

オペランドスタックに十分なオペランドがない場合は、演算子が2 + 3 + - （単項+と単項をサポートすることを決めない限り）です。または2 */3である。

24行目に到達すると、演算子スタックは空になり、オペランドスタックには単一の値、つまり最終結果が含まれているはずです。もしオペランドスタック上に複数の項目があるなら、あなたはあまりにも多くのオペランドを持っています（起こるべきではありません）。

したがって、24行目をオペランドスタックのポップに置き換えて、結果として返すことができます。

Shunting-yardは実際にあなたが言及した「再帰的語彙パーサー」の非常に単純化されたバージョンです。しかし、再帰によってスタックフレームを構築するのではなく、スタックを直接操作します。

これを行うコードを変更することはあまり難しくありません。以下はevaluateInfixと呼ばれるconvertToPostfix関数の修正版です。すべてが1回のパスで実行されます。私はPythonプログラマじゃないことに注意してくださいので、私は完璧に動作するようにコードを保証するものではありませんが、それはあなたのアイデアを与える必要があります。

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] 

evaluate機能は、オペレータと2つのオペランドを取り、操作を行います、結果を返します。したがって、('+', 3, 5)を指定すると、3+5を計算し、8を返します。

評価するたびに、2つのオペランドと1つの演算子を使用しています。

テストケース：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

がある場合は、文字のリストとして文字列を格納することができ、その後、直線的に2回実行し、最初に乗算/除算を計算してから加減算を行います。記号 -

すなわち、最初の反復では

1+10/2 -> 1 + 5 

はその後

1 + 5 -> 6 

を持ってこれも簡単にあなたが+またはで番号を追加するためにどのスタックで実装することができています。スタックに追加して、/または*に達したことを認識すると、前の要素がポップアップし、現在の数値で乗算または除算されて元に戻ります。最後に、スタック内のすべての要素の合計を求めます。

さらに、前の例では、使用されているスタックの唯一の要素が回答の直前にあるという観測を行うことができます。これは、合計を維持しながら前の要素を保存し、*または/の符号に達した場合は、合計から前の要素を減算して更新された要素を追加することができることを示しています。この方法は、O（1）余分なストレージを持つ1つのO（n）スキャンの問題を効果的に解決し、この問題の最適な解決策になる可能性があります。

Answer 3

@Jim MischelのソリューションをPython 3のコードとして公開しています。

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'))