# Go语言用栈实现算术表达式

xcltapestry · · 2474 次点击 · · 开始浏览

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

MAIL: xcl_168@aliyun.com

BLOG:http://blog.csdn/net/xcl168

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

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

MAIL: xcl_168@aliyun.com

BLOG:http://blog.csdn/net/xcl168