中缀表达式转换为后缀表达式 后缀表达式 做数学运算时,经常使用的是中缀表达式,即“操作数 运算符 操作数”。在计算机处理的时候更习惯后缀表达式,即“操作数 操作数 运算符”。例如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 }