今回は括弧付き四則演算のパーサを作ります。

この場合、カッコ内の式を先に処理する必要が出てきます。

BNFは次の通りです。

<数式> := <数式> + <項> | <数式> - <項> | <項>
<項> := <項> * <因子> | <項> / <因子> | <因子>
<因子> := <整数> | (<数式>)
<整数> := 0|1|2|3|4|5|6|7|8|9|<整数>

ここで因子の構文内に括弧付きの数式が定義されているため、

再帰関数等を使い括弧内の数式を処理してくことになります。

次のソースコードは数式の解析するためのクラスを定義し、

括弧が現れたときに、自身のクラスのインスタンスを生成してその続きから

対応する括弧の終わりまでを解析することで、再帰処理を解決しています。

ここでいう対応する括弧の終わりとは、

単純に末尾から近い括弧を示していることではありません。

例えば、次の式は注意が必要です。

1 + (2 + (3 + (4 + (5 + 6)) - 7) - 8) + 9

1つ目の'('に対応する括弧の終わりは確かに末尾から近い')'のですが、

2つ目の'('に対応する括弧の終わりは、数字7の後の')'であり、

必ずしも末尾から近い')'ではないことに注意してください。

こうした処理はスタックを利用して、カッコ内の数式を取り出して再帰処理する方法も取れます。

今回は')'が現れたときに、数式の読み取る位置のインデックス(idx)をあえてlen(入力した数式)にして、

強制的にその時点での値を返します。

動きを詳しく知りたい方は、

ソースコード上のコメントアウトを除いて実行してみると良いでしょう。

from collections import deque

class ExpressionParser():

  def __init__(self, idx = 0):
    self.idx = idx
    self.termList = deque([])
  
  def getIndex(self):
    return self.idx
  
  def calc(self, token):
#    print(self.termList, token)
    num1 = self.termList.pop()
    num2 = self.termList.pop()
    if token == '+':
      self.termList.append(num2 + num1)
    if token == '-':
      self.termList.append(num2 - num1)
    if token == '*':
      self.termList.append(num2 * num1)
    if token == '/':
      self.termList.append(num2 / num1)
    

  def getToken(self, expr):
    token = ''
    while True:
      if self.idx >= len(expr):
        break
      unit = expr[self.idx: self.idx + 1]
      if unit != ' ':
        if unit.isdigit():
          while unit.isdigit():
            token += unit
            self.idx += 1
            unit = expr[self.idx: self.idx + 1]
          self.idx -= 1
          break
        else:
          token = unit
          break
      self.idx += 1
#    print('get Token:',token)
    return token


  def parseExpression(self, expr):
    self.parseTerm(expr)
    token = self.getToken(expr)
    if len(token) == 0:
      return self.termList.pop()
#    print("parseExpression Token:", token)
    while token == '+' or token == '-':
      self.idx += 1
      self.parseTerm(expr)
      self.calc(token)
      token = self.getToken(expr)
    return self.termList.pop()
    
    
  def parseTerm(self, expr):
    self.parseFactor(expr)
    token = self.getToken(expr)
    if len(token) == 0:
      return
#    print("parseTerm Token:", token)
    while token == '*' or token == '/':
      self.idx += 1
      self.parseFactor(expr)
      self.calc(token)
      token = self.getToken(expr)


  def parseFactor(self, expr):
    token = self.getToken(expr)
#    print("parseFactor Token:", token)
    if token.isdigit():
      self.termList.append(int(token))
      self.idx += 1
    if token == '(':
      parser = ExpressionParser(self.idx + 1)
      token = parser.parseExpression(expr)
      self.idx = parser.getIndex() + 1
      self.termList.append(token)
    if token == ')':
      self.idx = len(expr)


if __name__ == '__main__':
  while True:
    print('Please input expression.(If finish this program, input "exit".):')
    expression = input()
    if expression == 'exit':
      break
    transaction = ExpressionParser()
    print("answer:", transaction.parseExpression(expression))
  

> python parser.py
Please input expression.(If finish this program, input "exit".):
4 * 3 + 2 * 1
answer: 14
Please input expression.(If finish this program, input "exit".):
3 * (2 / 2)
answer: 3.0
Please input expression.(If finish this program, input "exit".):
1 + (2 + (3 + (4 + (5 + 6)) - 7) - 8) + 9
answer: 15
Please input expression.(If finish this program, input "exit".):
1 * (2 * (3 * (4 * (5 + 6)) - 7) - 8) + 9
answer: 251
Please input expression.(If finish this program, input "exit".):
exit

>