### 今天看到知乎一个帖子,突然想 简单的实现一下这个算法
知乎上贴的图片是:
这个应该是属于编译原理方面的算法了，golang应该有语法分析工具，直接可以获得对应的语法拆解后的XX (相关概念一点也记不住了)
之所以发出来,是因为 写了两个多小时,各种条件,怎么这么麻烦啊. 希望可以和大家一起讨论下.
简易实现的代码为 (go test alg_test.go 测试即可):
```golang
//alg_test.go
package main
import (
"fmt"
"log"
"reflect"
"strconv"
"testing"
"unicode"
)
func assertEqual(t *testing.T, a, b interface{}) {
if reflect.DeepEqual(a, b) {
return
}
t.Errorf("AssertEqual not same:%v != %v\n", a, b)
}
func Test_Algorithm(t *testing.T) {
//0-9 +- */
assertEqual(t, Alg("1+2*3-4").String2(), "123*+4-")
assertEqual(t, Alg("1+2-3+4").String2(), "12+3-4+")
assertEqual(t, Alg("1*2/3*4").String2(), "12*3/4*")
assertEqual(t, Alg("1*2+3*4").String2(), "12*34*+")
assertEqual(t, Alg("1-2+3*4").String2(), "12-34*+")
assertEqual(t, Alg("1-2/3*4").String2(), "123/4*-")
assertEqual(t, Alg("1-2/3*4+5-6*7/8*9").String2(), "123/4*-5+67*8/9*-")
assertEqual(t, Alg("1+2*3-4").Calc(), 3)
assertEqual(t, Alg("1+2-3+4").Calc(), 4)
assertEqual(t, Alg("3*4/2*1").Calc(), 6)
assertEqual(t, Alg("1*2+3*4").Calc(), 14)
assertEqual(t, Alg("1-2+3*4").Calc(), 11)
assertEqual(t, Alg("1-4/2*4").Calc(), -7)
assertEqual(t, Alg("1-2/3*4").Calc(), 1)
assertEqual(t, Alg("1-2/3*4+5-6*7/8*9").Calc(), 1-2/3*4+5-6*7/8*9)
}
//后缀表达式
func Alg(input string) Stack {
log.Println("---------Alg Begin-----------")
var numStack, symStack Stack
curNum := []rune{}
for k, cur := range input {
isN := unicode.IsNumber(cur)
if k == 0 && isN == false {
panic("First must be number")
}
if isN {
curNum = append(curNum, cur)
if k == len(input)-1 {
numStack.Push(string(curNum))
log.Println(numStack, symStack)
checkPushSym(&numStack, &symStack, 0)
}
} else {
if k == len(input)-1 {
panic("Symbol mustn't the last one")
}
if len(curNum) == 0 {
panic("Symbol only support one")
}
numStack.Push(string(curNum))
curNum = make([]rune, 0)
log.Println(numStack, symStack)
//判断符号优先级
if numStack.Len() >= 2 {
checkPushSym(&numStack, &symStack, cur)
} else {
symStack.Push(string(cur))
log.Println(numStack, symStack)
}
}
}
if symStack.Len() > 0 {
numStack.PushVal(symStack.Pop())
log.Println("Final ", numStack, symStack)
}
return numStack
}
func checkPushSym(numStack *Stack, symStack *Stack, cur rune) {
if symStack.Len() == 0 {
if cur > 0 {
symStack.Push(string(cur))
}
return
}
needClearSymbol := func() bool {
if symStack.Len() > 1 {
return true
}
return false
}()
lastSym := symStack.Dump().String()
switch string(lastSym) {
case "*", "/", "%":
d := symStack.Pop()
numStack.PushVal(d)
switch string(cur) {
case "*", "/", "%":
log.Println(numStack, symStack)
symStack.Push(string(cur))
default:
if needClearSymbol {
log.Println(numStack, symStack)
d := symStack.Pop()
numStack.PushVal(d)
}
if cur > 0 {
log.Println(numStack, symStack)
symStack.Push(string(cur))
}
}
log.Println(numStack, symStack)
default:
if cur > 0 {
switch string(cur) {
case "*", "/", "%":
symStack.Push(string(cur))
log.Println(numStack, symStack)
default:
lastOne := symStack.Pop()
if needClearSymbol {
numStack.PushVal(lastOne)
log.Println(numStack, symStack)
symStack.Push(string(cur))
log.Println(numStack, symStack)
} else {
numStack.PushVal(lastOne)
log.Println(numStack, symStack)
symStack.Push(string(cur))
log.Println(numStack, symStack)
}
}
} else {
if needClearSymbol {
d := symStack.Pop()
numStack.PushVal(d)
log.Println("final", numStack, symStack)
} else {
d := symStack.Pop()
numStack.PushVal(d)
log.Println("final", numStack, symStack)
}
}
}
}
//================data struct=================
type Val string
type Stack struct {
datas []Val
}
func (this *Stack) Clear() {
this.datas = make([]Val, 0)
}
func (this *Stack) Push(v string) {
this.datas = append(this.datas, Val(v))
}
func (this *Stack) PushVal(v Val) {
this.datas = append(this.datas, Val(v))
}
func (this *Stack) Pop() Val {
if this.Len() == 0 {
panic("Len()==0 cannot pop")
}
v := this.datas[this.Len()-1]
this.datas = this.datas[0 : this.Len()-1]
return v
}
func (this *Stack) Dump() Val {
if this.Len() == 0 {
panic("Len()==0 cannot pop")
}
v := this.datas[this.Len()-1]
return v
}
func (this *Stack) Len() int {
return len(this.datas)
}
func (this Stack) String2() string {
ret := ""
for _, v := range this.datas {
ret += string(v)
}
return ret
}
func (this *Stack) Equal(another Stack) bool {
if this.Len() == another.Len() {
for k, v := range this.datas {
if v != another.datas[k] {
return false
}
}
return true
}
return false
}
func (this Stack) Calc() int {
log.Println("-----------calc----------")
var sum int
var numStack Stack
this = this.Revert()
log.Println("&& Revert=", this)
numStack.PushVal(this.Pop())
numStack.PushVal(this.Pop())
log.Println("&& numStack=", numStack)
for this.Len() > 0 {
v := this.Pop()
if v.IsSymbol() {
log.Println("&& Operator=", v)
a2, a1 := numStack.Pop(), numStack.Pop()
var a3 int
switch v {
case "+":
a3 = a1.Int() + a2.Int()
case "-":
a3 = a1.Int() - a2.Int()
case "*":
a3 = a1.Int() * a2.Int()
case "/":
a3 = a1.Int() / a2.Int()
}
numStack.Push(fmt.Sprintf("%v", a3))
log.Println("&& numStack=", numStack)
} else {
numStack.PushVal(v)
log.Println("&& numStack=", numStack)
}
}
sum = numStack.Pop().Int()
return sum
}
func (this Stack) Revert() Stack {
var r Stack
for this.Len() > 0 {
r.PushVal(this.Pop())
}
return r
}
func (this Val) String() string {
return string(this)
}
func (this Val) Int() int {
i, _ := strconv.Atoi(this.String())
return i
}
func (this Val) IsSymbol() bool {
switch this {
case "+", "-", "*", "/":
return true
}
return false
}
```
有疑问加站长微信联系（非本文作者）
