后缀表达式又叫做逆波兰表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,所以,这种表示法也称为中缀表示。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法。按此方法,每一运算符都置于其运算对象之后,故称为后缀表示。
运用后缀表达式进行计算的具体做法:
建立一个栈S 。从左到右读后缀表达式,如果读到操作数就将它压入栈S中,如果读到n元运算符(即需要参数个数为n的运算符)则取出由栈顶向下的n项按操作符运算,再将运算的结果代替原栈顶的n项,压入栈S中 。如果后缀表达式未读完,则重复上面过程,最后输出栈顶的数值则为结束。
计算机实现转换:
将中缀表达式转换为后缀表达式的算法思想:
- 开始扫描;
- 数字时,加入后缀表达式;
- 运算符:
a.若为最高级的运算符,入栈;
b. 若为 '(',入栈;
c. 若为 ')',则依次把栈中的的运算符加入后缀表达式中,直到出现'(',从栈中删除'(' ;
d. 若为不是最高级的运算符,则将从栈顶到第一个优先级不大于(小于,低于或等于)它的运算符(或 '(',但优先满足前一个条件)之间的运算符加入后缀表达式中,该运算符再入栈;
代码实现:
package com.wyp; import java.util.Stack; public class TestStack { private String testString = null; private Stack<Character> stack = null; /** * @author 397090770 * blog: * 转载请注明来源 * */ public TestStack(String testString) { this.testString = testString; this.stack = new Stack<Character>(); } private void analysisString() { for (int i = 0; i < testString.length(); i++) { char c = testString.charAt(i); if (c == '+' || c == '-') { if (stack.isEmpty() || stack.peek() == '(') { stack.push(c); } else { while (!stack.isEmpty() && (stack.peek() == '*' || stack.peek() == '/' || stack.peek() == '+' || stack.peek() == '-')) { System.out.print(stack.pop()); } stack.push(c); } } else if (c == '*' || c == '/') { if (stack.isEmpty() || stack.peek() == '+' || stack.peek() == '-' || stack.peek() == '(') { stack.push(c); } else { while (!stack.isEmpty() && (stack.peek() == '/' || stack.peek() == '*')) { System.out.print(stack.pop()); } stack.push(c); } } else if (c == '(') { stack.push(c); } else if (c == ')') { char temp = ' '; while ((temp = stack.pop()) != '(') { System.out.print(temp); } } else { System.out.print(c); } } if (!stack.isEmpty()) { while (!stack.isEmpty()) { System.out.print(stack.pop()); } } } public static void main(String[] args) { TestStack testStacknew = new TestStack("A+B*(C-D)/E+F/H"); testStacknew.analysisString(); } }
运行结果:ABCD-*E/+FH/+
本博客文章除特别声明,全部都是原创!原创文章版权归过往记忆大数据(过往记忆)所有,未经许可不得转载。
本文链接: 【中缀表达式转成后缀表达式实现】(https://www.iteblog.com/archives/161.html)