[置顶] 中缀表达式转成后缀表达式(含java实现的具体代码)

时间：2021-03-25 19:30:27

已转到：http://www.iteblog.com/archives/161

             后缀表达式又叫做逆波兰表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，所以，这种表示法也称为中缀表示。波兰逻辑学家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
 * */
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/+
（转载请注明：http://www.iteblog.com/archives/161，请不要用于商业目的。）
标签：

相关文章