将中序表达式转成后序表达式,再通过后序表达式计算出值。
package main //表达式 //author:Xiong Chuan Liang //date:2015-2-2 import ( "fmt" "github.com/xcltapestry/xclpkg/algorithm" "strconv" "errors" ) func main(){ // 中序表达式 后序表达式 // a+b = ab+ // (a+b)/c = ab+c/ // a+b*(c+d) = abcd+*+ // a*b+c*(d-e)/f = ab*cde-*f/+ //str := "a*b+c*(d-e)/f" //str := "1*2+3*(4-5)/6" str := "1*2+3*(5-1)/2" exp,err := ExpConvert(str) if err != nil { fmt.Println("中序表达式转后序表达式失败! ",err) }else{ Exp(exp) } //v := 1*2+3*(4-5)/6 v := 1*2+3*(5-1)/2 fmt.Println("标准结果: ",v) } func ExpConvert(str string)(string,error){ var result string stack := algorithm.NewStack() for _,s := range str { ch := string(s) if IsOperator(ch) { //是运算符 if stack.Empty() || ch == "(" { stack.Push(ch) }else{ if ch == ")" { //处理括号 for{ if stack.Empty() { return "",errors.New("表达式有问题! 没有找到对应的\"(\"号") } if stack.Top().(string) == "(" { break } result += stack.Top().(string) stack.Pop() } //弹出"(" stack.Top() stack.Pop() }else{ //非括号 //比较优先级 for{ if stack.Empty() { break } m := stack.Top().(string) if Priority(ch) > Priority(m) { break } result += m stack.Pop() } stack.Push(ch) } } }else{ //非运算符 result += ch } //end IsOperator() } //end for range str for { if stack.Empty() { break } result += stack.Top().(string) stack.Pop() } fmt.Println("ExpConvert() str = ",str ) fmt.Println("ExpConvert() result = ",result) return result,nil } func Exp(str string){ fmt.Println("\nCalc \nExp() :",str ) stack := algorithm.NewStack() for _,s := range str { ch := string(s) if IsOperator(ch) { //是运算符 if stack.Empty() { break } b := stack.Top().(string) stack.Pop() a := stack.Top().(string) stack.Pop() ia,ib := convToInt32(a,b) sv := fmt.Sprintf("%d",Calc(ch,ia,ib)) stack.Push( sv ) fmt.Println("Exp() ",a,"",ch,"",b,"=",sv) }else{ stack.Push(ch) fmt.Println("Exp() ch: ",ch) } //end IsOperator } //stack.Print() if !stack.Empty() { fmt.Println("表达式运算结果: ", stack.Top() ) stack.Pop() } } func convToInt32(a,b string)(int32,int32){ ia, erra := strconv.ParseInt(a, 10, 32) if erra != nil { panic(erra) } ib, errb := strconv.ParseInt(b, 10, 32) if errb != nil { panic(errb) } return int32(ia),int32(ib) } func IsOperator(op string)(bool){ switch(op){ case "(",")","+","-","*","/": return true default: return false } } func Priority(op string)(int){ switch(op){ case "*","/": return 3 case "+","-": return 2 case "(": return 1 default: return 0 } } func Calc(op string,a,b int32)(int32){ switch(op){ case "*": return (a * b) case "/": return (a / b) case "+": return (a + b) case "-": return (a - b) default: return 0 } }
运算结果:
ExpConvert() str = 1*2+3*(5-1)/2 ExpConvert() result = 12*351-*2/+ Calc Exp() : 12*351-*2/+ Exp() ch: 1 Exp() ch: 2 Exp() 1 * 2 = 2 Exp() ch: 3 Exp() ch: 5 Exp() ch: 1 Exp() 5 - 1 = 4 Exp() 3 * 4 = 12 Exp() ch: 2 Exp() 12 / 2 = 6 Exp() 2 + 6 = 8 表达式运算结果: 8 标准结果: 8
MAIL: xcl_168@aliyun.com
BLOG:http://blog.csdn/net/xcl168
有疑问加站长微信联系(非本文作者)