Skip to content

Instantly share code, notes, and snippets.

@liuliqiang
Created July 10, 2020 16:26
Show Gist options
  • Save liuliqiang/93e4eb03e5ab2f265cb59e0f5559a51d to your computer and use it in GitHub Desktop.
Save liuliqiang/93e4eb03e5ab2f265cb59e0f5559a51d to your computer and use it in GitHub Desktop.
四则运算表达式求值
package main
import (
"container/list"
"errors"
"fmt"
"strings"
)
var stackNumber list.List
var stackOp list.List
var DivZeroErr = errors.New("divider can not be 0")
func main() {
}
func eval(s string) (rtn float64, err error) {
s = strings.TrimSpace(s)
if len(s) == 0 {
return 0, nil
}
buildStack(s)
if err = calMultiDiv(); err != nil {
return 0, err
}
calAddSub()
return stackNumber.Remove(stackNumber.Front()).(float64), nil
}
func calMultiDiv() (err error) {
var tmpOp list.List
var tmpNumber list.List
for stackOp.Len() != 0 {
var op = stackOp.Remove(stackOp.Back())
switch op {
case uint8('+'):
fallthrough
case uint8('-'):
tmpOp.PushBack(op)
tmpNumber.PushBack(stackNumber.Remove(stackNumber.Back()))
case uint8('*'):
var num1 = stackNumber.Remove(stackNumber.Back()).(float64)
var num2 = stackNumber.Remove(stackNumber.Back()).(float64)
stackNumber.PushBack(num1 * num2)
case uint8('/'):
var num1 = stackNumber.Remove(stackNumber.Back()).(float64)
var num2 = stackNumber.Remove(stackNumber.Back()).(float64)
if num1 == 0.0 {
return DivZeroErr
}
stackNumber.PushBack(num2 / num1)
default:
panic(fmt.Sprintf("invalid op: %d", op))
}
}
for tmpOp.Len() != 0 {
stackOp.PushBack(tmpOp.Remove(tmpOp.Front()))
}
for tmpNumber.Len() != 0 {
stackNumber.PushBack(tmpNumber.Remove(tmpNumber.Front()))
}
return nil
}
func calAddSub() {
for stackOp.Len() != 0 {
var op = stackOp.Remove(stackOp.Back())
switch op {
case uint8('+'):
var num1 = stackNumber.Remove(stackNumber.Back()).(float64)
var num2 = stackNumber.Remove(stackNumber.Back()).(float64)
stackNumber.PushBack(num1 + num2)
case uint8('-'):
var num1 = stackNumber.Remove(stackNumber.Back()).(float64)
var num2 = stackNumber.Remove(stackNumber.Back()).(float64)
stackNumber.PushBack(num1 - num2)
}
}
}
func buildStack(s string) {
var number float64
for i := 0; i < len(s); i++ {
if isNumber(s[i]) {
number = number*10 + float64(s[i]-'0')
} else {
if number != 0.0 {
stackNumber.PushBack(number)
number = 0.0
}
if isOp(s[i]) {
stackOp.PushBack(s[i])
}
}
}
stackNumber.PushBack(number)
}
var opMap = map[uint8]bool{
'+': true,
'-': true,
'*': true,
'/': true,
}
func isOp(s uint8) bool {
var _, exists = opMap[s]
return exists
}
func isNumber(s uint8) bool {
return s >= '0' && s <= '9'
}
package main
import (
"fmt"
"testing"
)
func Test_eval(t *testing.T) {
for _, testCase := range []struct {
input string
output float64
err error
}{
{"2 * 5", 10, nil},
{"1+ 1", 2, nil},
{"1+ 1-1", 1, nil},
{"2/4 ", 0.5, nil},
{" ", 0, nil},
{" 11", 11, nil},
{" 1/0", 0, DivZeroErr},
} {
output, err := eval(testCase.input)
if output != testCase.output && err != testCase.err {
t.Error(fmt.Sprintf("%s expect %f, got: %f", testCase.input, testCase.output, output))
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment