LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ikuo0

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

Posted at

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

以前作った逆ポーランド記法のプログラムに変数という概念を追加します
以前の記事

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

# 入力
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

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

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 関数に代入演算子、区切り記号のトークンを追加します

  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 に全て移動させる処理を追加します

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

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

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

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

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

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 を参照することで答えを参照できます

以上です

ソースコード

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?