見出し画像

Try Go(Golang)字句解析プログラムを作ってみる(その１)

maybework

仕事でプログラミングコードを書く機会がなかなか無い今日この頃です。
機会がなければ欲しくなるのが人の世の常
毎年の、年末年始の行事として何かしら作るようにしています。

今回は、Go(Golang)で字句解析のプログラムを作成してみました。
目的は仕様書や設計書を作る必要の無いプログラミングを楽しむためとGo(Golang)を理解するためです。
技術的な要素や厳格性はありませんので手記として捉えていただきたいと思います。

Q:なぜ、Golangを選んだのか？
A:付き合ったことがないタイプと付き合ってみたかった、「Gopher（ゴーファー）くん」

チュートリアル

では、始めます。

初めの一歩

手始めに解析したい文字列は(3 + 4) * (1 - 2)です。
とりあえず、そのまま表示します。

//main.go
package main

import "fmt"

func main() {

	in := "(3 + 4) * (1 - 2)"

	fmt.Println(in)

}

中置記法の計算式っぽいのでなんか計算させてみたくなりました。

計算しやすいように中置記法から逆ポーランド記法に変換する

逆ポーランド記法に変換するにはStackがあると便利ですGoのStackを調べると・・・あ、無い、作ります。

中置記法の計算式を文字単位(データ型はrune)でStack構造体に格納します。

//Stack.go
package main

import (
	"container/list"
	"fmt"
)

type Stack struct {
	v *list.List
}

func NewStack() *Stack {
	return &Stack{v: list.New()}
}

func (s *Stack) Push(v interface{}) {
	s.v.PushBack(v)
}

func (s *Stack) Pop() rune {
	r := s.v.Back()
	if r == nil {
		return 0
	} else {
		return s.v.Remove(r).(rune)
	}
}

func (s *Stack) Last() rune {

	r := s.v.Back()
	if r != nil {
		return r.Value.(rune)
	} else {
		return 0
	}
}

func (s *Stack) Len() int {
	return s.v.Len()
}

動作確認

// main.go
package main

import "fmt"

func main() {

	in := "(3 + 4) * (1 - 2)"

	s := NewStack()

	for _, c := range in {
		s.Push(c)
	}

	fmt.Println("元の値:", in)
	fmt.Print("Stackの中身:")
	for 0 < s.Len() {
		fmt.Print(string(s.Pop()))
	}
	fmt.Print("\n")
}
元の値: (3 + 4) * (1 - 2)
Stackの中身:)2 - 1( * )4 + 3



入力、標準出力、スタックの整理


逆ポーランド記法に変換するには次のルールを設定する

  • 文字が'+' or '-'の場合：Stackの最後の値と比較し、文字>Stackの値の場合StackにPush

  • 文字が'+' or '-'の場合：Stackの最後の値と比較し、文字<Stackの値の場合StackからPopして表示、その後文字をStackにPush

  • 文字が'*' or '/'の場合：StackにPush

  • 文字が'('の場合StackにPush

  • 文字が')'の場合、StackからPopしてPopした文字が'('になるまで表示する

  • それ以外の場合、表示する

// main.go
package main

import (
	"fmt"
)

func Priority(c rune) int {

	switch c {
	case '*', '/':
		return 2
	case '+', '-':
		return 1
	default:
		return 0
	}
}

func ConvRPN(i interface{}) {
	s := NewStack()

	for _, c := range i.(string) {
		switch c {
		case '=':
			s.Push(c)
		case '+', '-':
			if Priority(c) > Priority(s.Last()) {
				s.Push(c)
			} else {
				fmt.Printf("%c", s.Pop())
				s.Push(c)
			}
		case '*', '/':
			s.Push(c)
		case '(':
			s.Push(c)
		case ')':
			for s.Len() > 0 {
				v := s.Pop()
				if v == '(' {
					break
				} else {
					fmt.Printf("%c", v)
				}
			}
		case ' ':
		default:
			fmt.Printf("%c", c)

		}
	}
	for s.Len() > 0 {
		fmt.Printf("%c", s.Pop())
	}
	fmt.Print("\n")

}

func main() {

	in := "(3 + 4) * (1 - 2)"
	ConvRPN(in)
}

逆ポーランドを文字列として扱うと次の問題が・・・
中置記法：(31+4)*(1-2)
逆ポーランド記法：314+12-*
中置記法：(3+14)*(1-2)
逆ポーランド記法：314+12-*

セパレーター文字列を使うのはMyルールとして無、数値と演算子単位で文字列としてリストに格納することにする。

まずは、rune型で格納していたStack.goをstringで格納するように変更

// Stack.go
package main

import (
	"container/list"
)

type Stack struct {
	v *list.List
}

func NewStack() *Stack {
	return &Stack{v: list.New()}
}

func (s *Stack) Push(v string) {
	s.v.PushBack(v)
}

func (s *Stack) Pop() string {
	r := s.v.Back()
	if r == nil {
		return ""
	} else {
		return s.v.Remove(r).(string)
	}
}

func (s *Stack) Last() string {

	r := s.v.Back()
	if r == nil {
		return ""

	} else {
		return r.Value.(string)
	}
}

func (s *Stack) Len() int {
	return s.v.Len()
}

共づれでPriorityの計算を修正

func Priority(c string) int {

	switch c {
	case "*", "/":
		return 2
	case "+", "-":
		return 1
	default:
		return 0
	}
}

修正前の確認

strings.Builderへの追加とリストへの書き出しを整理

続いて逆ポーランド記法変換を修正

func ConvRPN(i interface{}) *list.List {
	s := NewStack()
	l := list.New()
	var sb strings.Builder
	sb.Reset()

	for _, c := range i.(string) {
		switch c {
		case '=':
			s.Push(string(c))
		case '+', '-':
			if 0 < sb.Len() {
				l.PushBack(sb.String())
				sb.Reset()
			}
			if Priority(string(c)) > Priority(s.Last()) {
				s.Push(string(c))
			} else {
				l.PushBack(s.Pop())
				s.Push(string(c))
			}
		case '*', '/':
			if 0 < sb.Len() {
				l.PushBack(sb.String())
				sb.Reset()
			}
			s.Push(string(c))

		case '(':
			s.Push(string(c))
		case ')':
			if 0 < sb.Len() {
				l.PushBack(sb.String())
				sb.Reset()
			}

			for s.Len() > 0 {
				v := s.Pop()
				if v == "(" {
					break
				} else {
					l.PushBack(string(v))
				}
			}
		case ' ':
		default:
			sb.WriteRune(c)
		}
	}
	if 0 < sb.Len() {
		l.PushBack(sb.String())
		sb.Reset()
	}
	for s.Len() > 0 {
		l.PushBack(string(s.Pop()))
	}
	return l
}

計算処理を追加

func Calc(i interface{}) string {
	s := NewStack()
	for e := i.(*list.List).Front(); e != nil; e = e.Next() {
		switch e.Value {
		case "=":
		case "+":
			rhs, _ := strconv.ParseFloat(s.Pop(), 64)
			lhs, _ := strconv.ParseFloat(s.Pop(), 64)

			s.Push(strconv.FormatFloat(lhs+rhs, 'f', -1, 64))
			fmt.Println(strconv.FormatFloat(lhs, 'f', -1, 64), "+", strconv.FormatFloat(rhs, 'f', -1, 64), "=", s.Last())
		case "-":
			rhs, _ := strconv.ParseFloat(s.Pop(), 64)
			lhs, _ := strconv.ParseFloat(s.Pop(), 64)
			s.Push(strconv.FormatFloat(lhs-rhs, 'f', -1, 64))
			fmt.Println(strconv.FormatFloat(lhs, 'f', -1, 64), "-", strconv.FormatFloat(rhs, 'f', -1, 64), "=", s.Last())
		case "*":
			rhs, _ := strconv.ParseFloat(s.Pop(), 64)
			lhs, _ := strconv.ParseFloat(s.Pop(), 64)

			s.Push(strconv.FormatFloat(lhs*rhs, 'f', -1, 64))
			fmt.Println(strconv.FormatFloat(lhs, 'f', -1, 64), "*", strconv.FormatFloat(rhs, 'f', -1, 64), "=", s.Last())
		case "/":
			rhs, _ := strconv.ParseFloat(s.Pop(), 64)
			lhs, _ := strconv.ParseFloat(s.Pop(), 64)
			s.Push(strconv.FormatFloat(lhs/rhs, 'f', -1, 64))
			fmt.Println(strconv.FormatFloat(lhs, 'f', -1, 64), "/", strconv.FormatFloat(rhs, 'f', -1, 64), "=", s.Last())

		default:
			s.Push(e.Value.(string))
		}
	}
	ret := s.Pop()

	fmt.Println("=", ret)

	return ret
}

逆ポーランド記法の計算処理はすごくシンプルになります。

ここまでで、ざっくりと計算処理ができるようになりました、ここからさらにパワーアップして機能を盛り込みたいと思いますが今回はここまで
次回はさらに機能を盛り込んでいきたいと思います。

補足情報

フォルダ構成

フォルダ構成

ソースコードファイル

実行コマンド

maybework$go run .

--
The Gopher character is based on the Go mascot designed by Renée French.

この記事が気に入ったらサポートをしてみませんか？