逆ポーランド記法電卓に変数を追加

# 逆ポーランド記法電卓に変数を追加
以前作った逆ポーランド記法のプログラムに変数という概念を追加します
[以前の記事](https://qiita.com/ikuo0/items/561ade15966fde1130ce)

以下のような入出力となります

``` python3
# 入力
a = 6 + (4 * (3 + 2)) - 7 + 4; b = (10 / 2) - (3 + (4 * 2)); c = a * b;

# 出力
{'a': 15.0, 'b': -6.0, 'c': -90.0}
```

# 追加部分の解説

末尾にソース全体を記載していますので解説中に出てくる関数についてはそちらを参照してください

## 代入演算子（＝）、区切り記号（；）の追加

区切り記号が必要な理由は区切り記号が無いと代入処理がどこからどこまでか判断しづらくなるからです
改行を区切り記号としても良いのですが、プログラミング言語の明確な区切りと言えばセミコロンだろうと思いましたのでセミコロンとしました
go言語 や python のように区切り記号が無くても動作するスクリプト言語もありますが、曖昧さを回避するためにセミコロンがあったほうが良いと考えます

＝　は　EQUAL
；　は　SEPARATOR

としてトークン定義を追加します

``` python3
class TokenIdDefine(enum.Enum):
  NOP           = enum.auto()
  SEPARATOR     = enum.auto()
  NUMBER        = enum.auto()
  IDENTITY      = enum.auto()
  PLUS          = enum.auto()
  MINUS         = enum.auto()
  MULTIPLE      = enum.auto()
  DIVISION      = enum.auto()
  EQUAL         = enum.auto()
  BEGIN_BRACKET = enum.auto()
  END_BRACKET   = enum.auto()
  
  CALCULATED    = enum.auto()
  ERROR         = enum.auto()
```

## トークン解析処理の追加

toTokensAndValues 関数に代入演算子、区切り記号のトークンを追加します

``` python3
  tokenRules = [
      [r"^\s+", TokenIdDefine.NOP],
      [r"^;", TokenIdDefine.SEPARATOR],
      [r"^\d+", TokenIdDefine.NUMBER],
      [r"^[a-zA-Z][\w]*", TokenIdDefine.IDENTITY],
      [r"^\+", TokenIdDefine.PLUS],
      [r"^\-", TokenIdDefine.MINUS],
      [r"^\*", TokenIdDefine.MULTIPLE],
      [r"^\/", TokenIdDefine.DIVISION],
      [r"^\=", TokenIdDefine.EQUAL],
      [r"^\(", TokenIdDefine.BEGIN_BRACKET],
      [r"^\)", TokenIdDefine.END_BRACKET],
  ]
```

## 区切り記号が現れたらスタック処理を一旦終わらせる

infixNotationToReversePolishNotation 関数に SEPARATOR が現れたら stack を output に全て移動させる処理を追加します

``` python3
    if len(stack) > 0 and inputToken == TokenIdDefine.SEPARATOR:
      output.extend(list(reversed(stack)))
      stack = []
      inputIndex += 1
      continue
```

## 逆ポーランド記法の計算処理の変更

以前の簡易電卓では入力、スタックともに「数値」しか扱いませんでしたが、変数を追加することにより「数値」と「変数」が現れるようになりました
数値であればそのまま扱い、文字列であったら変数として扱うよう関数を修正します

単語構成文字が出現したら辞書型変数の variables に変数を格納します
計算式の途中で単語構成文字が出現したらそれをキーとして変数 variable から値を取り出します

token でその文字列が何者かを判断し itemToNumber 関数で値をそのまま使うか変数からの取り出しかを選択します

``` python3
def itemToNumber(value, variables):
  if isinstance(value, float):
    return value
  elif isinstance(value, str) and value in variables:
    return variables[value]
  else:
    return float(value)

def calcReversePolishNotation(size, rpnTokens, rpnValues):
  stack: typing.List[TokenValuePair] = []
  variables = {}
  for i in range(size):
    token = rpnTokens[i]
    value = rpnValues[i]
    if token in [TokenIdDefine.NUMBER, TokenIdDefine.IDENTITY, TokenIdDefine.CALCULATED]:
      stack.append(TokenValuePair(token=token, value=value))
    else:
      rhs = stack.pop()
      lhs = stack.pop()
      if token == TokenIdDefine.PLUS:
        value = itemToNumber(lhs.value, variables) + itemToNumber(rhs.value, variables)
        stack.append(TokenValuePair(token=TokenIdDefine.CALCULATED, value=value))
      elif token == TokenIdDefine.MINUS:
        value = itemToNumber(lhs.value, variables) - itemToNumber(rhs.value, variables)
        stack.append(TokenValuePair(token=TokenIdDefine.CALCULATED, value=value))
      elif token == TokenIdDefine.MULTIPLE:
        value = itemToNumber(lhs.value, variables) * itemToNumber(rhs.value, variables)
        stack.append(TokenValuePair(token=TokenIdDefine.CALCULATED, value=value))
      elif token == TokenIdDefine.DIVISION:
        value = itemToNumber(lhs.value, variables) / itemToNumber(rhs.value, variables)
        stack.append(TokenValuePair(token=TokenIdDefine.CALCULATED, value=value))
      elif token == TokenIdDefine.EQUAL:
        variables[str(lhs.value)] = float(rhs.value)
  return stack, variables
```

## 結果の見方
前回とは異なり stack, variables をそのまま返しています
単純な計算式であれば stack[-1] を参照すれば答えが参照できます
変数に格納した場合は variables を参照することで答えを参照できます

以上です

# ソースコード

``` python3
import re
import sys
import enum
import typing
import dataclasses

class TokenIdDefine(enum.Enum):
  NOP           = enum.auto()
  SEPARATOR     = enum.auto()
  NUMBER        = enum.auto()
  IDENTITY      = enum.auto()
  PLUS          = enum.auto()
  MINUS         = enum.auto()
  MULTIPLE      = enum.auto()
  DIVISION      = enum.auto()
  EQUAL         = enum.auto()
  BEGIN_BRACKET = enum.auto()
  END_BRACKET   = enum.auto()
  
  CALCULATED    = 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 = [
      [r"^\s+", TokenIdDefine.NOP],
      [r"^;", TokenIdDefine.SEPARATOR],
      [r"^\d+", TokenIdDefine.NUMBER],
      [r"^[a-zA-Z][\w]*", TokenIdDefine.IDENTITY],
      [r"^\+", TokenIdDefine.PLUS],
      [r"^\-", TokenIdDefine.MINUS],
      [r"^\*", TokenIdDefine.MULTIPLE],
      [r"^\/", TokenIdDefine.DIVISION],
      [r"^\=", TokenIdDefine.EQUAL],
      [r"^\(", TokenIdDefine.BEGIN_BRACKET],
      [r"^\)", 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.IDENTITY:      9,
      TokenIdDefine.PLUS:          5,
      TokenIdDefine.MINUS:         5,
      TokenIdDefine.MULTIPLE:      7,
      TokenIdDefine.DIVISION:      7,
      TokenIdDefine.BEGIN_BRACKET: 8,
      TokenIdDefine.EQUAL:         9,
      TokenIdDefine.END_BRACKET:   0,
      TokenIdDefine.NOP:           1,
      TokenIdDefine.ERROR:         999,
  }
  tokenIdToStackPriority = {
      TokenIdDefine.NUMBER:        9,
      TokenIdDefine.IDENTITY:      9,
      TokenIdDefine.PLUS:          4,
      TokenIdDefine.MINUS:         4,
      TokenIdDefine.MULTIPLE:      7,
      TokenIdDefine.DIVISION:      7,
      TokenIdDefine.BEGIN_BRACKET: 1,
      TokenIdDefine.EQUAL:         2,
      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 and inputToken == TokenIdDefine.SEPARATOR:
      output.extend(list(reversed(stack)))
      stack = []
      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

@dataclasses.dataclass
class TokenValuePair:
  token:  TokenIdDefine = None
  value:  typing.Any = None

def itemToNumber(value, variables):
  if isinstance(value, float):
    return value
  elif isinstance(value, str) and value in variables:
    return variables[value]
  else:
    return float(value)

def calcReversePolishNotation(size, rpnTokens, rpnValues):
  stack: typing.List[TokenValuePair] = []
  variables = {}
  for i in range(size):
    token = rpnTokens[i]
    value = rpnValues[i]
    if token in [TokenIdDefine.NUMBER, TokenIdDefine.IDENTITY, TokenIdDefine.CALCULATED]:
      stack.append(TokenValuePair(token=token, value=value))
    else:
      rhs = stack.pop()
      lhs = stack.pop()
      if token == TokenIdDefine.PLUS:
        value = itemToNumber(lhs.value, variables) + itemToNumber(rhs.value, variables)
        stack.append(TokenValuePair(token=TokenIdDefine.CALCULATED, value=value))
      elif token == TokenIdDefine.MINUS:
        value = itemToNumber(lhs.value, variables) - itemToNumber(rhs.value, variables)
        stack.append(TokenValuePair(token=TokenIdDefine.CALCULATED, value=value))
      elif token == TokenIdDefine.MULTIPLE:
        value = itemToNumber(lhs.value, variables) * itemToNumber(rhs.value, variables)
        stack.append(TokenValuePair(token=TokenIdDefine.CALCULATED, value=value))
      elif token == TokenIdDefine.DIVISION:
        value = itemToNumber(lhs.value, variables) / itemToNumber(rhs.value, variables)
        stack.append(TokenValuePair(token=TokenIdDefine.CALCULATED, value=value))
      elif token == TokenIdDefine.EQUAL:
        variables[str(lhs.value)] = float(rhs.value)
  return stack, variables


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

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, stack, variables = calc(a)
    answerConfirm = eval(infixNotation)
    rpnString = " ".join([str(token) for token in rpnTokens])
    print("infix notation {}, rpn {}, answer={}, confirm answer={}".format(infixNotation, b, stack[-1].value, answerConfirm))

def test2():
  sourceCode = "a = 6 + (4 * (3 + 2)) - 7 + 4; b = (10 / 2) - (3 + (4 * 2)); c = a * b;"
  tokens, values = toTokensAndValues(sourceCode)
  #tokensString = [str(token) for token in tokens]
  #print(tokensString)
  
  output = infixNotationToReversePolishNotation(tokens)
  rpnTokens = indexing(tokens, output)
  rpnValues = indexing(values, output)
  #rpnTokensString = " ".join([str(token) for token in rpnTokens])
  #print(rpnTokensString)
  #valuesString = " ".join([str(value) for value in rpnValues])
  #print(valuesString)
  
  stack, variables = calcReversePolishNotation(len(rpnTokens), rpnTokens, rpnValues)
  print(stack)
  print(variables)

def main():
  #test1()
  test2()

if __name__ == "__main__":
  main()

```