首页 > 代码库 > 中序表达式转后序表式式
中序表达式转后序表式式
中序表达式转后序表式式:
将中序表达式所有括号补全,然后将所有运算符向右移出无匹配的第一个右括号,去掉括号即为后序表式式
- 举例:
- 原式:a+b*(c+d/e)
- 补全括号:(a+(b*(c+(d/e))))
- 操作符右移:(a(b(c(de)/)+)*)+
- 去掉括号:abcde/+*+
中序表达式转前序表式式:
将中序表达式所有括号补全,然后将所有运算符向左移出无匹配的第一个左括号,去掉括号即为前序表式式
- 举例:
- 原式:a+b*(c+d/e)
- 补全括号:(a+(b*(c+(d/e))))
- 操作符右移:+(a*(b+(c/(de))))
- 去掉括号:+a*b+c/de
-
算法:
利用运算符栈(OPTR)和数据栈(OPND)将中缀表达式转化为后缀表达式。
将结束标志字符’#’放入操作符栈(OPTR);
从中缀表达式pre左端依次读取pre[i]:- 1.若pre[i]为操作数,压入数据栈(OPND);
- 2.若pre[i]为左括号,压入操作符栈(OPTR);
- 3.若pre[i]为右括号,则将操作符栈(OPTR)中的运算符依次出栈并压入数据栈(OPND),直到遇到左括号为止,但是该左括号出栈但不压入数据栈(OPND)
- 4.若pre[i]为操作符:
(1)若操作符栈(OPTR)为空,将此操作符pre[i]压入数据栈(OPND);
(2)若pre[i]的优先级大于操作符栈(OPTR)顶的优先级,将此操作符pre[i]压入数据栈(OPND);
(3)若操作符栈(OPTR)不为空且pre[i]的优先级小于等于操作符栈(OPTR)顶的优先级,将操作符栈(OPTR)中的运算符依次出栈并压入数据栈(OPND),直到不满足条件,此操作符pre[i]压入数据栈(OPND)
直到遍历完整个中序表达式之后,操作符栈(OPTR)中仍然存在运算符,那么将这些运算符依次出栈加入到数据栈(OPND)中,直到栈为空。
按照上述步骤完成后,将操作符栈(OPTR)逆序即可得到逆波兰表达式。
中序表达式转后序表式式
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。