Go 运算表达式求值

[TOC]

运算表达式参考学习韩老师的golang教程.

设计思路

采用golang实现常用的表达式求值,不包含括号,这边暂时没有实现.

数据结构使用Stack如下,使用两个栈分别来存储操作数和运算符.

const MaxTop = 30
type Stack struct {
	Top int
	arr [MaxTop]int
}

思考需要解决哪些问题才能解决表达式求值呢?

如何读取表达式的运算符和操作数.
操作符和运算数如何进行比较
如何使得操作数每次运算都能安装优先来进行运算

为了解决上面的三个问题,思考如下.

// 1. 设计一个算法,读取表达式中的每个字符.对表达式进行切分,我们知道string类型底层实现为slice切片.
每取一个字符,对index++,循环读取即可完成对每个操作运算符的提取.

ch := exp[index : index+1] // "3" 单个字符串, "+" ==> 43

// 2. 将单个字符串转为ASCII对应的十进制数. 

temp := int([]byte(ch)[0]) // 字符串转为byte,  

/* 3. 对取出来的每个ASCII的十进制数进行判断,如果为操作数,则直接入操作数栈
如果为运算符,则需要进行判断:
a. 如果符号栈为空,则符号栈直接入栈.
b. 如果符号栈不为空,则进行比对,如果
	A. 当前符号栈顶的运算符优先级 >= 要入栈的运算符优先级, 从符号栈弹出一个运算符,从操作数栈弹出两个数,进行运算,运算结果存入操作数栈. (这里需要循环比对,如果不循环比对,+ * - * -,最后没有办法求解)
	B. 当前符号栈顶的运算符优先级 < 要入栈的运算符优先级,则直接入符号栈.
4. 执行这些后,当前操作数栈和符号栈的栈底到栈顶的优先级,始终是从低到高,每次弹出2个操作数,一个运算符,进行计算后,将结果压入操作数栈,循环操作,最后一个存入的操作数即为结果.
*/

这里有个漏洞,如果是多位数操作怎么办,这样的思路就错了,每次读入一位数,最后的结果肯定不是我们所想.

进行运算和判断的方法

// 1.判断Stack为空方法

func (s *Stack) IsEmpty() bool {
	return s.Top == -1 
}

// 2. 判断Stack已满方法
func (s *Stack) IsFull() bool {
	return s.Top == MaxTop-1
}

// 3. 判断Stack的大小方法
func (s *Stack) Size() int {
	return len(arr[:s.Top])
}

// 4. 入栈
func (s *Stack) Push(val int) bool {
	if s.IsFull() {
		return false
	}
	s.Top++
	s.arr[s.Top]= val
	return true
}

// 5. 出栈
func (s *Stack) Pop()(val int, bool) {
	if s.IsEmpty() {
		returnn -1, false
	}
	val = s.arr[s.Top]
	s.Top--
	return val, true
}
// 6. 判断是否为运算符
func (s *Stack) IsOpr(val int) bool {
	if val == 42 || val == 43 || val == 45 ||
		val == 47 || val == 94 {
		return true
	}	
	return false
}
// 7.0 计算幂(整形)
func power(a, n int) int {
	res := 1
	if n != 0 {
		res *= a
		n--
	}
	retuen res
}
// 7. 计算操作数与运算符
func (s *Stack) Cal(a, b, opr int) (res int) {
	switch opr {
	case 42: 
		res = b * a
	case 43: 
		res = b + a
	case 45:
		res = b - a
	case 47:
		res = b / a
	case 94:
		res = power(b, a) // b^a
	}
	return res
}

// 8. 定义运算符的优先级
func (s *Stack) Nice(opr int) (res int) {
	switch {
	case opr == 43 || opr == 45:  // * / 
		res = 1 
	case opr == 94:   // ^
		res = 2
	case opr == 42 || opr == 47: // + -
		fallthough	
    default:   
        res = 0
	}
	return res
}

Exp求值

如果给出的exp符合表达式,那么结果一定存在.

func Exp(exp string) (res int) {
		numStack := &Stack{
		Top: -1,
	}
	oprStack := &Stack{
		Top: -1,
	}
	index, a, b, opr, res := 0, 0, 0, 0, 0
	keepNum := ""
	for {
		ch := exp[index : index+1] // "3" 单个字符串, "+" ==> 43
		fmt.Println(ch)
		temp := int([]byte(ch)[0]) //字符串转为byte,  字符转的ASCII码
		if oprStack.IsOpr(temp) {  // 如果是数字,则进入数字处理逻辑.
			// 如果operStack是空栈,直接入栈;
			// 并将数栈也pop出两个数,进行运算,
			// 将运算的结果push到数栈,符号再入符号栈
			if oprStack.IsEmpty() {
				oprStack.Push(temp)
			} else {
				//不是空栈的话,如果栈顶的运算符优先级,
				//大于当前准备入栈的运算符优先级,先pop出栈
				//例如 栈顶运算符为 * ,准备 入栈的运算符为 + ,
				//则先出栈. 并从操作栈取出两个操作数进行运算,
				//再把结果压入操作栈==>
				//继续进行比较, 如果栈顶的运算符优先级大于
				//当前准备入栈的运算符优先级,先pop出栈.
                //直到栈为空.或者栈的优先级从低到高排列.
				for oprStack.Nice(oprStack.arr[oprStack.Top]) >=
					oprStack.Nice(temp) {
					a, _ = numStack.Pop()
					b, _ = numStack.Pop()
					opr, _ = oprStack.Pop()
					res = oprStack.Cal(a, b, opr)
					//运算结果重新入数栈
					numStack.Push(res)
                    // 弹出opr运算符之后,进行判空处理,为空就直接跳出循环
                    // 直接将待入栈的运算符压入符号栈.
					if oprStack.IsEmpty() {
						break
					}
				}
				oprStack.Push(temp)
			}

		} else { //数字,如何处理多位数的逻辑.
			//处理多位数 keepNum string,拼接.
			keepNum += ch
			if index == len(exp)-1 {
                // 如果是最后的一个数,则直接将str '3' ==> 转换为int 3
				val, _ := strconv.ParseInt(keepNum, 10, 64)
				numStack.Push(int(val)) // 3 ==> 51(ASCII)
			} else {
				if oprStack.IsOpr(int([]byte(exp[index+1 : index+2])[0])) {
                    // 如果下一个字符是运算符,则直将keepNum压入操作数栈.
                    // 否则就一直进行keepNum += ch 拼接操作.
					val, _ := strconv.ParseInt(keepNum, 10, 64)
					numStack.Push(int(val)) // 3 ==> 51(ASCII)
                    // 操作数入栈后,keep置空.
					keepNum = ""
				}
			}
		}
		// 判断index是否已经扫完
		if index+1 == len(exp) {
			break
		}
		index++
	}

	// 优先级高的已经计算完,或者优先级从低到高在符号栈排列.

	for { //符号栈为空就跳出循环,这时候操作数栈最后的一个数肯定就是exp的结果.
		if oprStack.IsEmpty() {
			break
		}
		a, _ = numStack.Pop()
		b, _ = numStack.Pop()
		opr, _ = oprStack.Pop()
		res = oprStack.Cal(a, b, opr)
		//运算结果重新入数栈
		numStack.Push(res)
	}

	res, _ = numStack.Pop()
	return res
}

验证

给出一个表达式,来进行验证.

func main() {
	exp := "30+30*6-4^2-6"
	res := Exp(exp)
	fmt.Printf("exp %s = %v", exp, res)
}
/*output
exp 30+30*6-4^2-6 = 188
*/

整体的代码

package main

import (
	"fmt"
	"strconv"
)

const MaxTop = 30

type Stack struct {
	Top int
	arr [MaxTop]int
}

func (s *Stack) IsEmpty() bool {
	return s.Top == -1
}

func (s *Stack) IsFull() bool {
	return s.Top == MaxTop-1
}

func (s *Stack) Size() int {
	return len(s.arr[:s.Top])
}

func (s *Stack) Push(val int) (b bool) {
	if s.IsFull() {
		return false
	}
	s.Top++
	s.arr[s.Top] = val
	fmt.Printf("stack push  %#v\n", val)
	return true
}

func (s *Stack) Pop() (val int, b bool) {
	if s.IsEmpty() {
		return 0,false
	}
	val = s.arr[s.Top]
	s.Top--
	fmt.Printf("stach pop %#v\n", val)
	return val, true
}

func (s *Stack) List() {
	if s.IsEmpty() {
		return
	}
	//for k,v :=range s.arr {
	//	defer fmt.Printf("arr[%d] = %d\n",k,v)
	//}
	fmt.Println("Stack -->")
	for i := s.Top; i >= 0; i-- {
		fmt.Printf("arr[%d] = %d\n", i, s.arr[i])
	}
}

// 判断是否为运算符[+,-,*,/,^]
func (s *Stack) IsOpr(val int) bool {
	/* ASCII '42 * 43 + 45 - 47 /' */
	if val == 42 || val == 43 || val == 45 || val == 47 || val == 94 {
		return true
	} else {
		return false
	}

}

func Power(a, n int) int {
	res := 1
	for n != 0 {
		res *= a
		n--
	}
	return res
}

func (s *Stack) Cal(a, b, opr int) int {
	res := 0
	switch opr {
	case 42:
		res = b * a
	case 43:
		res = b + a
	case 45:
		res = b - a
	case 47:
		res = b / a
	case 94:
		res = Power(b, a) // b^a
	default:
		fmt.Println("opr is err")
	}
	return res
}

// 编写方法,返回运算符的优先级[自定义]

func (s *Stack) Nice(opr int) int {
	/* * / Nice返回1
	   + - Nice返回0	
	   ^   Nice返回2*/
	res := 0
	if opr == 42 || opr == 47 {
		return 1
	} else if opr == 43 || opr == 45 {
		return 0
	} else if opr == 94 { // 94	^
		return 2
	}
	return res
}

func Exp(exp string) (res int) {
	numStack := &Stack{
		Top: -1,
	}
	oprStack := &Stack{
		Top: -1,
	}
	index, a, b, opr, res := 0, 0, 0, 0, 0
	keepNum := ""
	for {
		ch := exp[index : index+1] // "3" 单个字符串, "+" ==> 43
		temp := int([]byte(ch)[0]) //字符串转为byte,  字符转的ASCII码
		if oprStack.IsOpr(temp) {  // 如果是数字,则进入数字处理逻辑.
			// 如果operStack是空栈,直接入栈;
			// 并将数栈也pop出两个数,进行运算,
			// 将运算的结果push到数栈,符号再入符号栈
			if oprStack.IsEmpty() {
				oprStack.Push(temp)
			} else {
				//不是空栈的话,如果栈顶的运算符优先级,
				//大于当前准备入栈的运算符优先级,先pop出栈
				//例如 栈顶运算符为 * ,准备 入栈的运算符为 + ,
				//则先出栈. 并从操作栈取出两个操作数进行运算,
				//再把结果压入操作栈==>
				//继续进行比较, 如果栈顶的运算符优先级大于
				//当前准备入栈的运算符优先级,先pop出栈.
                //直到栈为空.或者栈的优先级从低到高排列.
				for oprStack.Nice(oprStack.arr[oprStack.Top]) >=
					oprStack.Nice(temp) {
					a, _ = numStack.Pop()
					b, _ = numStack.Pop()
					opr, _ = oprStack.Pop()
					res = oprStack.Cal(a, b, opr)
					//运算结果重新入数栈
					numStack.Push(res)
                    // 弹出opr运算符之后,进行判空处理,为空就直接跳出循环
                    // 直接将待入栈的运算符压入符号栈.
					if oprStack.IsEmpty() {
						break
					}
				}
				oprStack.Push(temp)
			}

		} else { //数字,如何处理多位数的逻辑.
			//处理多位数 keepNum string,拼接.
			keepNum += ch
			if index == len(exp)-1 {
                // 如果是最后的一个数,则直接将str '3' ==> 转换为int 3
				val, _ := strconv.ParseInt(keepNum, 10, 64)
				numStack.Push(int(val)) // 3 ==> 51(ASCII)
			} else {
				if oprStack.IsOpr(int([]byte(exp[index+1 : index+2])[0])) {
                    // 如果下一个字符是运算符,则直将keepNum压入操作数栈.
                    // 否则就一直进行keepNum += ch 拼接操作.
					val, _ := strconv.ParseInt(keepNum, 10, 64)
					numStack.Push(int(val)) // 3 ==> 51(ASCII)
                    // 操作数入栈后,keep置空.
					keepNum = ""
				}
			}
		}
		// 判断index是否已经扫完
		if index+1 == len(exp) {
			break
		}
		// 每次扫完都必须index++,扫描下一个exp
		index++
	}

	// 优先级高的已经计算完,或者优先级从低到高在符号栈排列.

	for { //符号栈为空就跳出循环,这时候操作数栈最后的一个数肯定就是exp的结果.
		if oprStack.IsEmpty() {
			break
		}
		a, _ = numStack.Pop()
		b, _ = numStack.Pop()
		opr, _ = oprStack.Pop()
		res = oprStack.Cal(a, b, opr)
		//运算结果重新入数栈
		numStack.Push(res)
	}

	res, _ = numStack.Pop()
	return res
}

func main() {
	exp := "30+30*6-4^2-6"
	res := Exp(exp)
	fmt.Printf("exp %s = %v", exp, res)
}

//stack push  30
//stack push  43
//stack push  30
//stack push  42
//stack push  6
//stack push  180
//stack push  210
//stack push  45
//stack push  4
//stack push  94
//stack push  2
//stack push  16
//stack push  194
//stack push  45
//stack push  6
//stack push  188
//exp 30+30*6-4^2-6 = 188

参考

韩顺平golang教程.
数据结构与算法

Go 运算表达式求值

设计思路

进行运算和判断的方法

Exp求值

验证

参考

Tags:

文章推荐