中缀表达式转换为后缀表达式

后缀表达式

做数学运算时，经常使用的是中缀表达式，即“操作数 运算符 操作数”。在计算机处理的时候更习惯后缀表达式，即“操作数 操作数 运算符”。例如a + b * c转换为后缀表达式a b c * +，使用栈可以将中缀表达式转换为后缀表达式，具体的方法为：

  • 扫描到数字直接输出
  • 扫描到运算符则与栈顶比较，若扫描到的运算符优先级低于或等于栈顶运算符的优先级，则弹栈直到栈空或栈顶运算符优先级低于扫描到的运算符，之后运算符入栈；否则直接入栈。
  • 若扫描到)，则一直弹栈直到(出栈

代码实现——调用链表栈

数据结构

1
2
3
4
type Stack_data struct {
	Num int
	Op  string
}

运算符优先级MAP

使用一个全局变量map保存各个运算符的优先级

1
2
3
4
5
6
var priority_dict = map[string]int{
	"+": 0,
	"-": 0,
	"*": 1,
	"/": 1,
	"(": -1}

结构体

1
2
3
4
type To_postfix struct {
	data_stack base_stack.Link_stack
	result     []base_stack.Stack_data
}

方法

计算优先级

根据栈顶运算符优先级和传入运算符优先级比较，确定传入的运算符是否直接入栈

1
2
3
4
5
6
7
8
func (t *To_postfix) priority_compute(in_data base_stack.Stack_data) bool {
	if t.data_stack.Is_empty() {
		return true
	} else {
		top_data, _ := t.data_stack.Get_head()
		return priority_dict[in_data.Op] > priority_dict[top_data.Op]
	}
}

数字处理

数字不入栈，直接进入结果切片

1
2
3
func (t *To_postfix) handle_num(in_data base_stack.Stack_data) {
	t.result = append(t.result, in_data)
}

左括号处理

左括号直接入栈

1
2
3
func (t *To_postfix) handle_left_bracket(in_data base_stack.Stack_data) {
	t.data_stack.Push(in_data)
}

右括号处理

右括号不入栈，弹栈直到一个左括号出栈

1
2
3
4
5
6
7
func (t *To_postfix) handle_right_bracket(in_data base_stack.Stack_data) {
	top_data, err := t.data_stack.Pop()
	for err == nil && top_data.Op != "(" {
		t.result = append(t.result, top_data)
		top_data, err = t.data_stack.Pop()
	}
}

运算符处理

1
2
3
4
5
6
7
8
9
func (t *To_postfix) handle_op(in_data base_stack.Stack_data) {
	tempdata := base_stack.Stack_data{}
	can_insert := t.priority_compute(in_data)
	for !can_insert {
		tempdata, _ = t.data_stack.Pop()
		t.result = append(t.result, tempdata)
	}
	t.data_stack.Push(in_data)
}

总处理方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func (t *To_postfix) Handle(din []base_stack.Stack_data) {
	var temp base_stack.Stack_data
	for i := range din {
		switch din[i].Op {
		case "n":
			t.handle_num(din[i])
		case "(":
			t.handle_left_bracket(din[i])
		case ")":
			t.handle_right_bracket(din[i])
		default:
			t.handle_op(din[i])
		}
	}
	for !t.data_stack.Is_empty() {
		temp, _ = t.data_stack.Pop()
		t.result = append(t.result, temp)
	}
}

结果返回函数

1
2
3
func (t *To_postfix) Return_result() []base_stack.Stack_data {
	return t.result
}

构造函数

1
2
3
4
5
6
func New_to_post() *To_postfix {
	link := *base_stack.New_link_stack()
	topost := To_postfix{}
	topost.data_stack = link
	return &topost
}

后缀表达式的计算

计算方法

后缀表达式的计算比较简单，顺序扫描整个后缀表达式：

  • 若遇到数字，直接入栈
  • 若遇到运算符，弹栈两次取出两个数字，按运算符运算，将结果再次入栈

这样扫描完整个后缀表达式之后，栈中就应该只有一个数，弹栈即可得到结果

代码实现

结构体

1
2
3
type Compute struct {
	data_stack base_stack.Link_stack
}

运算符处理方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func (c *Compute) operator(op base_stack.Stack_data) int {
	data1, _ := c.data_stack.Pop()
	data2, _ := c.data_stack.Pop()
	switch op.Op {
	case "+":
		return data1.Num + data2.Num
	case "-":
		return data1.Num - data2.Num
	case "*":
		return data1.Num * data2.Num
	case "":
		return data1.Num / data2.Num
	default:
		return data1.Num
	}
}

运算方法

1
2
3
4
5
6
7
8
9
func (c *Compute) Compute(expression []base_stack.Stack_data) {
	for i := range expression {
		if expression[i].Op == "n" {
			c.data_stack.Push(expression[i])
		} else {
			c.data_stack.Push(base_stack.Stack_data{c.operator(expression[i]), "n"})
		}
	}
}

结果返回方法

1
2
3
4
func (c *Compute) Result() int {
	result, _ := c.data_stack.Pop()
	return result.Num
}