编译原理 后缀表达式 算法 简易实现

ayanmw · · 2581 次点击 · 开始浏览    置顶
这是一个创建于 的主题,其中的信息可能已经有所发展或是发生改变。

### 今天看到知乎一个帖子,突然想 简单的实现一下这个算法 知乎上贴的图片是: ![v2-63b5c3c3f7867541a4bb4f6a8dc2b8a3_b.jpg](https://static.studygolang.com/200506/36ce2e56a5418beb0160fd5bc73e9d8f.jpg) 这个应该是属于编译原理方面的算法了,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 } ```

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

2581 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传