逆ポーランド記法への変換を実装してみる

なんらかの言語を作りたくなったのでflexとbisonを調べていたら、結局諸々の実装は自力でやらないといけないことが分かり、そんなに作るなら全部自分で作ったほうが楽じゃない？と思いスタックマシンの作り方とか調べてました
逆ポーランド記法が良いとのことで調べて実装してみました

参考にしたサイト
https://qiita.com/phenan/items/df157fef2fea590e3fa9
https://zenn.dev/peg/articles/79a4823d86c21e

中置記法の計算式文字列を逆ポーランド記法（後置記法）に変換してから計算するプログラムを作成しました
四則演算と括弧に対応しています
以下ソース

import re
import sys
import enum
import typing

class TokenIdDefine(enum.Enum):
  NOP = enum.auto()
  NUMBER = enum.auto()
  PLUS = enum.auto()
  MINUS = enum.auto()
  MULTIPLE = enum.auto()
  DIVISION = enum.auto()
  BEGIN_BRACKET = enum.auto()
  END_BRACKET = enum.auto()
  ERROR = enum.auto()

def indexing(array, indexes):
  res = []
  for i in indexes:
    res.append(array[i])
  return res

def matchToken(tokenRules: typing.List[typing.List], infixNotation: str, index: int) -> typing.Tuple[typing.Any, int]:
  for tokenRule in tokenRules:
    regexp, token = tokenRule
    match = re.match(regexp, infixNotation[index:])
    if match != None:
      return token, match.end()
  return TokenIdDefine.ERROR, 0

def toTokensAndValues(infixNotation):
  tokenRules = [
      ["^\s+", TokenIdDefine.NOP],
      ["^\d+", TokenIdDefine.NUMBER],
      ["^\+", TokenIdDefine.PLUS],
      ["^\-", TokenIdDefine.MINUS],
      ["^\*", TokenIdDefine.MULTIPLE],
      ["^\/", TokenIdDefine.DIVISION],
      ["^\(", TokenIdDefine.BEGIN_BRACKET],
      ["^\)", TokenIdDefine.END_BRACKET],
  ]
  tokens = []
  values = []
  index = 0
  while(index < len(infixNotation)):
    token, size = matchToken(tokenRules=tokenRules, infixNotation=infixNotation, index=index)
    if token == TokenIdDefine.ERROR or size <= 0:
      print("error on {} character".format(index))
      break
    value = infixNotation[index:index + size]
    tokens.append(token)
    values.append(value)
    index += size
  return tokens, values

def infixNotationToReversePolishNotation(tokens):
  tokenIdToInputPriority = {
      TokenIdDefine.NUMBER:        9,
      TokenIdDefine.PLUS:          4,
      TokenIdDefine.MINUS:         4,
      TokenIdDefine.MULTIPLE:      6,
      TokenIdDefine.DIVISION:      6,
      TokenIdDefine.BEGIN_BRACKET: 8,
      TokenIdDefine.END_BRACKET:   0,
      TokenIdDefine.NOP:           1,
      TokenIdDefine.ERROR:         999,
  }
  tokenIdToStackPriority = {
      TokenIdDefine.NUMBER:        9,
      TokenIdDefine.PLUS:          5,
      TokenIdDefine.MINUS:         5,
      TokenIdDefine.MULTIPLE:      7,
      TokenIdDefine.DIVISION:      7,
      TokenIdDefine.BEGIN_BRACKET: 1,
      TokenIdDefine.END_BRACKET:   0,
      TokenIdDefine.NOP:           1,
      TokenIdDefine.ERROR:         999,
  }
  output = []
  stack = []
  size = len(tokens)
  inputIndex = 0
  while(inputIndex < size):
    inputToken = tokens[inputIndex]
    if inputToken == TokenIdDefine.NOP:
      inputIndex += 1
      continue
    if inputToken == TokenIdDefine.END_BRACKET:
      while len(stack) > 0 and (tokens[stack[-1]] != TokenIdDefine.BEGIN_BRACKET):
        poped = stack.pop()
        output.append(poped)
      if len(stack) > 0:
        stack.pop()
      inputIndex += 1
      continue

    if len(stack) == 0 or tokenIdToInputPriority[inputToken] > tokenIdToStackPriority[tokens[stack[-1]]]:
      stack.append(inputIndex)
      inputIndex += 1
    else:
      poped = stack.pop()
      output.append(poped)
  output.extend(list(reversed(stack)))
  return output

def calcReversePolishNotation(size, rpnTokens, rpnValues):
  stack = []
  for i in range(size):
    token = rpnTokens[i]
    value = rpnValues[i]
    if token == TokenIdDefine.NUMBER:
      stack.append(float(value))
    else:
      rhs = stack.pop()
      lhs = stack.pop()
      if token == TokenIdDefine.PLUS:
        stack.append(lhs + rhs)
      elif token == TokenIdDefine.MINUS:
        stack.append(lhs - rhs)
      elif token == TokenIdDefine.MULTIPLE:
        stack.append(lhs * rhs)
      elif token == TokenIdDefine.DIVISION:
        stack.append(lhs / rhs)
  return stack[-1]


def calc(infixNotation):
  tokens, values = toTokensAndValues(infixNotation)
  output = infixNotationToReversePolishNotation(tokens)
  rpnTokens = indexing(tokens, output)
  rpnValues = indexing(values, output)
  answer = calcReversePolishNotation(len(rpnTokens), rpnTokens, rpnValues)
  return infixNotation, rpnTokens, rpnValues, answer

def test1():
  samples = [
      ["(1 + 2) * 3", "1 2 + 3 *"],
      ["(4 + 5) * (6 - 3)", "4 5 + 6 3 - *"],
      ["((7 - 2) + 5) * 4", "7 2 - 5 + 4 *"],
      ["8 * (3 + (2 * 5))", "8 3 2 5 * + *"],
      ["(4 * 5) + (3 - 2)", "4 5 * 3 2 - +"],
      ["3 + 4 * 2 / (1 - 5)", "3 4 2 * 1 5 - / +"],
      ["(10 + 5) * (8 - (2 + 6))", "10 5 + 8 2 6 + - *"],
      ["(10 / 2) - (3 + (4 * 2))  ", "10 2 / 3 4 2 * + -"],
      ["(5 + (5 * 10) / 2) - 3", "5 5 10 * 2 / + 3 -"],
      ["6 + (4 * (3 + 2)) - 7", "6 4 3 2 + * + 7 -"],
  ]
  for (a, b) in samples:
    infixNotation, rpnTokens, rpnValues, answer = calc(a)
    answerConfirm = eval(infixNotation)
    rpnString = " ".join([str(token) for token in rpnTokens])
    print("infix notation {}, rpn {}, answer={}, confirm answer={}".format(infixNotation, b, answer, answerConfirm))

def main():
  test1()

if __name__ == "__main__":
  main()

# https://qiita.com/phenan/items/df157fef2fea590e3fa9
# https://zenn.dev/peg/articles/79a4823d86c21e

主要部分だけ解説

infixNotationToReversePolishNotation 関数について解説していきます
infixNotationToReversePolishNotation 関数は構文解析済みのトークン配列を受け取り逆ポーランド記法のルールで並び替えたインデックスの配列を返します

優先度定義

参考サイトに記載してあるように数値、演算子に優先度を定義します、input -> (stack or output) の判定に使用します

# infixNotationToReversePolishNotation 関数、優先度定義
def infixNotationToReversePolishNotation(tokens):
  tokenIdToInputPriority = {
      TokenIdDefine.NUMBER:        9,
      TokenIdDefine.PLUS:          4,
      TokenIdDefine.MINUS:         4,
      TokenIdDefine.MULTIPLE:      6,
      TokenIdDefine.DIVISION:      6,
      TokenIdDefine.BEGIN_BRACKET: 8,
      TokenIdDefine.END_BRACKET:   0,
      TokenIdDefine.NOP:           1,
      TokenIdDefine.ERROR:         999,
  }
  tokenIdToStackPriority = {
      TokenIdDefine.NUMBER:        9,
      TokenIdDefine.PLUS:          5,
      TokenIdDefine.MINUS:         5,
      TokenIdDefine.MULTIPLE:      7,
      TokenIdDefine.DIVISION:      7,
      TokenIdDefine.BEGIN_BRACKET: 1,
      TokenIdDefine.END_BRACKET:   0,
      TokenIdDefine.NOP:           1,
      TokenIdDefine.ERROR:         999,
  }
  output = []
  stack = []
  size = len(tokens)
  inputIndex = 0

終わり括弧の出現処理

入力に終わり括弧が出現したら、stackを始まりの括弧が現れるまで取り出してoutputに追加します

  while(inputIndex < size):
    inputToken = tokens[inputIndex]
    if inputToken == TokenIdDefine.NOP:
      inputIndex += 1
      continue
    if inputToken == TokenIdDefine.END_BRACKET:
      while len(stack) > 0 and (tokens[stack[-1]] != TokenIdDefine.BEGIN_BRACKET):
        poped = stack.pop()
        output.append(poped)
      if len(stack) > 0:
        stack.pop()
      inputIndex += 1
      continue

入力とスタックの優先度を見て stack か output を振り分ける

冒頭で宣言した数値・演算子の優先度を比較して「stackに追加するか」か「stackからoutputに追加するか」を振り分けます

    if len(stack) == 0 or tokenIdToInputPriority[inputToken] > tokenIdToStackPriority[tokens[stack[-1]]]:
      stack.append(inputIndex)
      inputIndex += 1
    else:
      poped = stack.pop()
      output.append(poped)

最後はstackをひっくり返してoutputにくっつける

最後にstackに残っている数値をoutputにひっくり返してからくっつけます、これは　popしてappendを繰り返すを省略した作業です

  output.extend(list(reversed(stack)))
  return output

以上です、各所で解説されてるので詳細はそれらを参照してください