栈的应用中缀表达式转换为后缀表达式后缀表达式的计算
栈的应用中缀表达式转换为后缀表达式后缀表达式的计算
月见樽
发布于 2018-04-27 12:04:30
发布于 2018-04-27 12:04:30
中缀表达式转换为后缀表达式
后缀表达式
做数学运算时，经常使用的是中缀表达式，即“操作数 运算符 操作数”。在计算机处理的时候更习惯后缀表达式，即“操作数 操作数 运算符”。例如a + b * c转换为后缀表达式a b c * +，使用栈可以将中缀表达式转换为后缀表达式，具体的方法为：
- 扫描到数字直接输出
- 扫描到运算符则与栈顶比较，若扫描到的运算符优先级低于或等于栈顶运算符的优先级，则弹栈直到栈空或栈顶运算符优先级低于扫描到的运算符，之后运算符入栈；否则直接入栈。
- 若扫描到
)，则一直弹栈直到(出栈
代码实现——调用链表栈
数据结构
type Stack_data struct {
Num int
Op string
}运算符优先级MAP
使用一个全局变量map保存各个运算符的优先级
var priority_dict = map[string]int{
"+": 0,
"-": 0,
"*": 1,
"/": 1,
"(": -1}结构体
type To_postfix struct {
data_stack base_stack.Link_stack
result []base_stack.Stack_data
}方法
计算优先级
根据栈顶运算符优先级和传入运算符优先级比较，确定传入的运算符是否直接入栈
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]
}
}数字处理
数字不入栈，直接进入结果切片
func (t *To_postfix) handle_num(in_data base_stack.Stack_data) {
t.result = append(t.result, in_data)
}左括号处理
左括号直接入栈
func (t *To_postfix) handle_left_bracket(in_data base_stack.Stack_data) {
t.data_stack.Push(in_data)
}右括号处理
右括号不入栈，弹栈直到一个左括号出栈
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()
}
}运算符处理
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)
}总处理方法
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)
}
}结果返回函数
func (t *To_postfix) Return_result() []base_stack.Stack_data {
return t.result
}构造函数
func New_to_post() *To_postfix {
link := *base_stack.New_link_stack()
topost := To_postfix{}
topost.data_stack = link
return &topost
}后缀表达式的计算
计算方法
后缀表达式的计算比较简单，顺序扫描整个后缀表达式：
- 若遇到数字，直接入栈
- 若遇到运算符，弹栈两次取出两个数字，按运算符运算，将结果再次入栈
这样扫描完整个后缀表达式之后，栈中就应该只有一个数，弹栈即可得到结果
代码实现
结构体
type Compute struct {
data_stack base_stack.Link_stack
}运算符处理方法
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
}
}运算方法
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"})
}
}
}结果返回方法
func (c *Compute) Result() int {
result, _ := c.data_stack.Pop()
return result.Num
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017.12.03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录