/**
* GenericLinkedStack.java
*/
package fix;
import java.util.EmptyStackException;
/**
*泛型的链式栈数据结构
*/
public class GenericLinkedStack
// 栈顶元素
private Item top = null;
// 返回栈顶元素,并弹出
public E pop() throws EmptyStackException {
if (isEmpty()) {
throw new EmptyStackException();
}
E e = top.value;
top = top.next;
return e;
}
/**
* 栈顶压入一个元素
* @param e 被压入的元素
*/
public void push(E e) {
Item curr = new Item(e);
curr.next = top;
top = curr;
}
/**
* 返回栈顶元素,但不出栈
* @return 栈顶元素
*/
public E peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return top.value;
}
/**
* 判断栈是否为空
* @return 判断结果
*/
public boolean isEmpty() {
return top == null;
}
/**
* 栈中元素
* @author jilen
*
*/
class Item {
//元素
private E value;
//下一个
private Item next;
public Item(E e) {
this.value = e;
}
public E getValue() {
return value;
}
public void setValue(E value) {
this.value = value;
}
public Item getNext() {
return next;
}
public void setNext(Item next) {
this.next = next;
}
}
}
/**
* InfixToPostfixConverter.java
*/
package fix;
import java.util.Hashtable;
/**
* @author jilen
*
*/
public class InfixToPostfixConverter {
// 操作符及其优先级组成的键值对
private static final Hashtable
private StringBuffer infix;
private StringBuffer postfix;
GenericLinkedStack
// 初始化操作符列表,static语句块会在加载类时自动执行
static {
operators = new Hashtable
operators.put('^', 4);
operators.put('*', 3);
operators.put('/', 3);
operators.put('%', 3);
operators.put('+', 2);
operators.put('-', 2);
operators.put('(', -1);
operators.put(')', 5);
}
/**
*
*/
public InfixToPostfixConverter(StringBuffer infix, StringBuffer postfix) {
this.infix = infix;
this.postfix = postfix;
}
/**
* 转换函数
*/
public void convertToPostfix() {
// 对输入字符串中字符遍历
for (int i = 0, n = infix.length(); i < n; i++) {
char c = infix.charAt(i);
// 是数字之间添加到转换后字符串
if (isNumber(c)) {
postfix.append(c);
} else if (isOperator(c)) {
switch (c) {
// '(' 直接入栈
case '(':
stack.push(c);
break;
// ')' 弹出元素直到碰到'('
case ')':
while (!stack.isEmpty() && stack.peek() != '(') {
postfix.append(stack.pop());
}
stack.pop();
break;
// 其他操作符
default:
// 当前操作符比栈顶操作符优先级高,直接入栈
if (stack.isEmpty() || precedence(c, stack.peek())) {
stack.push(c);
}
// 当前操作符比栈顶操作符优先级低,出栈直到为空或栈顶优先级低于当前操作符
else if (!precedence(c, stack.peek())) {
while (!stack.isEmpty() && !precedence(c, stack.peek())) {
postfix.append(stack.pop());
}
stack.push(c);
}
break;
}
}
}
// 若栈中还有操作符,所以元素出栈
while (!stack.isEmpty()) {
postfix.append(stack.pop());
}
}
/**
* 判断是否为操作符
* @param c
* @return
*/
public static boolean isOperator(char c) {
return operators.containsKey(c);
}
/**
* 优先级大小关系operator1 > operator2 则返回true,否则false
* @param operator1
* @param operator2
* @return 判断结果
*/
public static boolean precedence(char operator1, char operator2) {
return operators.get(operator1) > operators.get(operator2);
}
/**
* 是否数字
* @param c 要判断的字符
* @return 判断结果
*/
public static boolean isNumber(char c) {
return c >= '0' && c <= '9';
}
}
/**
*Main.java测试类
*/
package fix;
/**
* @author Administrator
*
*/
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
StringBuffer infix = new StringBuffer("(1+2)*3/4");
StringBuffer postfix = new StringBuffer();
InfixToPostfixConverter converter = new InfixToPostfixConverter(infix,
postfix);
converter.convertToPostfix();
System.out.println(postfix.toString());
}
}
中缀转后缀的程序,有GenericLinkedStack.java,InfixToPostfix.java,Main.java三个源文件需要放在fix包下
呵呵 这个程序挺长的,你的分太少了呀