Shunting-Yard法を使って電卓のプログラムを作ってみた
はじめに
みなさんこんにちは、村人です。ゆくゆくは電卓アプリを作りたいので、今回はその前段階としてShunting-Yard法を使って数式を計算するプログラムを書いたのでその備忘録です。 リポジトリはこちら
どう使えるか
競技プログラミングなどで計算機についてのプログラミングが出題されることがあったり、実際に電卓を作る際に必要になったりします。
Shunting-Yard法（操車場アルゴリズム）とは
Shunting-Yard法を使うと、計算結果を簡単に取得できるだけでなく、逆ポーランド記法に簡単に変更することができます。実際のコードは後述しますが、被演算子と演算子でスタックを分けて、計算順序を考えながら計算していきます。
考え
これを使って数式を計算する考えとしては以下のようになります。
while トークンがある:
if トークンが数字
オペランドスタックへpush
if トークンが関数
演算子スタックへpush
if トークンが演算子
while ((演算子スタックの一番上が関数)
|| (演算子スタックの一番上が計算順序のより高い演算子)
|| (演算子スタックの一番上が計算順序の同じ演算子))
&& (演算子スタックの一番上が左カッコじゃない)
演算子スタックと被演算子スタックから取り出して計算
被演算子スタックが足りない場合はエラー
演算子スタックへpush
if トークンが"("
演算子スタックへpush
if トークンが")"
while 演算子スタックの一番上が"("ではない
演算子スタックと被演算子スタックから取り出して計算
被演算子スタックが足りない場合はエラー
"("を演算子スタックから取り出す
if "("が見つからなかった
エラー
if 演算子スタックが残っている
エラー
コード
今回は一番描き慣れているTypescriptで書いていきますが、他の言語でももちろん可能です。 また今回は、可読性やカプセル化のためにクラス型を使用しています。また逆ポーランド記法の数式を出力できるようにもします。
import * as isNumber from 'is-number'
type Token = { precedence?: number, LeftAssociative?: Boolean, func: (a: number, b: number) => number }
type Func = { func: (a: number, b?: number) => number, binary: boolean }
export default class Calculator {
private readonly operatorsStack: string[] = []
private readonly output: number[] = []
private postfix: string[] = []
private result: number
constructor(tokensOrStr: string[] | string) {
const tokens = [
'(',
...(tokensOrStr instanceof Array) ?
(tokensOrStr as string[]) :
(tokensOrStr as string).trim().split(' ').filter(a => a !== ''),
')'
]
for (let i = 0, len = tokens.length; i < len; i++) {
const token = tokens[i]
if (isNumber(token)) {
this.postfix.push(token)
this.output.push(+token)
}
else if (this.isFunc(token)) {
this.operatorsStack.push(token)
}
else if (this.isOperator(token)) {
let top = this.operatorsStack[this.operatorsStack.length - 1]
while (top !== undefined && top !== '(' && (
this.isFunc(token) ||
(Calculator.operators[token].LeftAssociative &&
(Calculator.operators[token].precedence <= Calculator.operators[top].precedence)) ||
(!Calculator.operators[token].LeftAssociative &&
(Calculator.operators[token].precedence < Calculator.operators[top].precedence))
)) {
top = this.calc()
}
this.operatorsStack.push(token)
}
else if (token === '(') {
this.operatorsStack.push(token)
}
else if (token === ')') {
while (this.operatorsStack[this.operatorsStack.length - 1] !== '(') {
this.calc()
}
this.operatorsStack.pop()
}
else {
throw new Error('unexpected character.\nMaybe you forgot the space or mistype func name')
}
}
if (this.output.length > 1) throw new Error('too much parameter')
this.result = this.output.pop()
}
calc() {
const op = this.operatorsStack.pop()
if (this.isOperator(op)) {
const b = this.output.pop()
const a = this.output.pop()
if (a === undefined || b === undefined) throw new Error('less parameter')
this.output.push(Calculator.operators[op].func(+a, +b))
}
else if (this.isFunc(op)) {
if (Calculator.funcs[op].binary) {
const b = this.output.pop()
const a = this.output.pop()
if (a === undefined || b === undefined) throw new Error('less parameter')
this.output.push(Calculator.funcs[op].func(+a, +b))
}
else {
const a = this.output.pop()
if (a === undefined) throw new Error('less parameter')
this.output.push(Calculator.funcs[op].func(+a))
}
}
this.postfix.push(op)
return this.operatorsStack[this.operatorsStack.length - 1]
}
get getResult() {
return this.result
}
static readonly funcs: { [key: string]: Func } = Object.freeze(
{
'sqrt': {
func: a => Math.sqrt(a),
binary: false
},
'log': {
func: (a, b) => Math.log(b) / Math.log(a),
binary: true
},
'log10': {
func: a => Math.log10(a),
binary: false
},
'ln': {
func: a => Math.log(a),
binary: false
},
'sin': {
func: (a) => Math.sin(a),
binary: false
},
cos: {
func: a => Math.cos(a),
binary: false
},
tan: {
func: a => Math.tan(a),
binary: false
},
'nthrt': {
func: (a, b) => Math.pow(a, 1 / b),
binary: true
}
}
)
static readonly operators: { [key: string]: Token } = Object.freeze(
{
'+': {
precedence: 1,
LeftAssociative: true,
func: (a, b) => a + b
},
'-': {
precedence: 1,
LeftAssociative: true,
func: (a, b) => a - b
},
'*': {
precedence: 2,
LeftAssociative: true,
func: (a, b) => a * b
},
'/': {
precedence: 2,
LeftAssociative: true,
func: (a, b) => a / b
},
'^': {
precedence: 3,
LeftAssociative: false,
func: (a, b) => Math.pow(a, b)
}
}
)
isOperator(token: string) {
return Calculator.operators.hasOwnProperty(token)
}
isFunc(token: string) {
return Calculator.funcs.hasOwnProperty(token)
}
get getPostfix() {
return this.postfix
}
}
使用例
import * as isNumber from 'is-number'
import Calculator from './calculator'
console.log(new Calculator('1 + 3 * 2 ^ 3 - 1').getResult)
拡張
今回はテスト段階でまだ関数を網羅していないのでfuncsオブジェクトにプロパティを追加して増やすことができます。
最後に
ここまでご覧いただきまことにありがとうございます。 今回このプログラムを使うことで比較的簡単に計算機のプログラムを書くことができました。次はこれを使って電卓サイトや電卓アプリを作っていければと思います。