四则运算的中缀转后缀，逆波兰表达式求值

首先描述问题

给定一个字符串
example:"4-(4-3*5+(2*4)+100)/10";
要求输出结果"-5.70";结果四舍五入，保留两位小数

首先进行的是括号优先级的处理

	public BigDecimal calculateString(String str) {
		char[] strs = str.toCharArray();
		Stack<String> stack = new Stack<String>();

		for (int i = 0; i < strs.length; i++) {
			String stackStr = String.valueOf(strs[i]);
			stack.push(stackStr);
			if (")".equals(stack.top())) {
				String subStr = null;
				while (!"(".equals(stack.top())) {
					stack.pop();
					if (!"(".equals(stack.top())) {
						subStr = addEnd(subStr, stack.top());
					}
				}
				String pushStr = CalculateReversePolishExpression(subStr);
				stack.pop();
				stack.push(pushStr);
			}

		}
		String resultStr = null;
		while (stack.count != 0) {
			resultStr = CalculateReversePolishExpression(stack.toString());
		}
		BigDecimal result = null;
		if (resultStr != null) {
			result = new BigDecimal(resultStr);
		} else {
			result = BigDecimal.ZERO;
		}
		return result.setScale(2, BigDecimal.ROUND_HALF_UP);
	}

将每个字符逐一进栈，当扫描到")"时，进行出栈操作，直到栈顶元素等于"("
并记录出栈的"("与")"之间的字符串为subStr
然后是对subStr求后缀表达式，并计算结果
也就是这句代码

String pushStr = CalculateReversePolishExpression(subStr);

再把结果进栈
最后stack的内容是去掉括号的一个四则表达式
再进行一次CalculateReversePolishExpression方法，则得到最终结果

中缀转后缀表达式的基本思路
基本思路如下：
用一个链表 List<String> 储存将要生成的后缀表达式
用一个栈 Stack<String> 储存操作符
判断当前节点， 如果是操作数， 直接加入后缀表达式中， 如果是操作符，则比较前一个操作符和当前操作符的优先级，
如果前一个操作符优先级较高，则将前一个操作符加入后缀表达式中，否则将操作符压入操作符栈，如果遇到反括号 ')', 则在操作符栈中反向搜索，直到遇到匹配的正括号为止，将中间的操作符依次加到后缀表达式中。

然后是后缀表达式的计算

遍历储存后缀表达式的链表，将元素依次进栈，当遇到操作符时，连续出栈两个元素，进行运算，再将结果进栈，最后栈内留下的元素就是计算结果

最后再贴出茫茫多的代码

package graph;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * 
 * 应用：逆波兰表达式
 * 
 * @author Leon.Chen
 * 
 */
public class CalculateString {

	public BigDecimal calculateString(String str) {
		char[] strs = str.toCharArray();
		Stack<String> stack = new Stack<String>();

		for (int i = 0; i < strs.length; i++) {
			String stackStr = String.valueOf(strs[i]);
			stack.push(stackStr);
			if (")".equals(stack.top())) {
				String subStr = null;
				while (!"(".equals(stack.top())) {
					stack.pop();
					if (!"(".equals(stack.top())) {
						subStr = addEnd(subStr, stack.top());
					}
				}
				String pushStr = CalculateReversePolishExpression(subStr);
				stack.pop();
				stack.push(pushStr);
			}

		}
		String resultStr = null;
		while (stack.count != 0) {
			resultStr = CalculateReversePolishExpression(stack.toString());
		}
		BigDecimal result = null;
		if (resultStr != null) {
			result = new BigDecimal(resultStr);
		} else {
			result = BigDecimal.ZERO;
		}
		return result.setScale(2, BigDecimal.ROUND_HALF_UP);
	}

	public String[] matcher(String regex, String str) {
		Pattern pattern = Pattern.compile(regex);
		Matcher matcher = pattern.matcher(str);
		List<String> list = new ArrayList<String>();
		while (matcher.find()) {
			list.add(matcher.group());
		}
		String[] result = new String[list.size()];
		return list.toArray(result);
	}

	public List<String> createReversePolishExpression(String subStr) {
		String regex = "\\d+\\.{0,1}\\d*";
		String[] numbers = matcher(regex, subStr);
		String changeStr = subStr.replaceAll(regex, "0").replaceAll("\\-\\-0",
				"-1").replaceAll("\\+\\-0", "+1").replaceAll("\\*\\-0", "*1")
				.replaceAll("\\/\\-0", "/1");
		char[] chars = changeStr.toCharArray();
		int index = 0;
		List<String> list = new ArrayList<String>();
		for (int i = 0; i < chars.length; i++) {
			String str = String.valueOf(chars[i]);
			if ("0".equals(str)) {
				list.add(numbers[index++]);
			} else if ("1".equals(str)) {
				list.add("-" + numbers[index++]);
			} else {
				list.add(str);
			}
		}
		List<String> suffix = new ArrayList<String>();
		Stack<String> operator = new Stack<String>();
		for (int i = 0; i < list.size(); i++) {
			if (!isOperatorType(list.get(i))) {
				suffix.add(list.get(i));
			} else {
				if (operator.count == 0) {
					operator.push(list.get(i));
				} else {
					while (operator.count != 0&&compare(operator.top(), list.get(i)) >= 0) {
						String top = operator.top();
						operator.pop();
						suffix.add(top);
					} 
					operator.push(list.get(i));

				}
			}
		}

		while (operator.count != 0) {
			suffix.add(operator.top());
			operator.pop();
		}
		return suffix;
	}

	public String CalculateReversePolishExpression(String subStr) {
		List<String> suffix = createReversePolishExpression(subStr);
		Stack<Double> stack = new Stack<Double>();
		for (int i = 0; i < suffix.size(); i++) {
			if (!isOperatorType(suffix.get(i))) {
				stack.push(Double.valueOf(suffix.get(i)));
			} else {
				Double current = stack.top();
				stack.pop();
				Double previous = null;
				if (stack.count != 0) {
					previous = stack.top();
					stack.pop();
				} else {
					previous = new Double(0);
				}
				Double result = calculate(suffix.get(i), previous, current);
				stack.push(result);
			}
		}
		return stack.top().toString();
	}

	public String addEnd(String str, String a) {
		StringBuffer buf = new StringBuffer();
		buf.append(a);
		if (str != null) {
			buf.append(str);
		}
		return buf.toString();
	}

	public boolean isOperatorType(String str) {
		if (str.equals("+") || str.equals("-") || str.equals("*")
				|| str.equals("/")) {
			return true;
		}
		return false;
	}

	public int compare(String op1, String op2) {
		Integer iop1 = getOperator(op1);
		Integer iop2 = getOperator(op2);
		return iop1.compareTo(iop2);
	}

	public Integer getOperator(String op) {
		if ("+".equals(op) || "-".equals(op)) {
			return new Integer(0);
		}
		if ("*".equals(op) || "/".equals(op)) {
			return new Integer(1);
		}
		return null;
	}

	public Double calculate(String op, Double previous, Double current) {
		if ("+".equals(op)) {
			return previous + current;
		}
		if ("-".equals(op)) {
			return previous - current;
		}
		if ("*".equals(op)) {
			return previous * current;
		}
		if ("/".equals(op)) {
			return previous / current;
		}
		return null;
	}

	public static void main(String[] args) {
		String[] strs = new String[]{"(5+6)*7","(-1)/(-3)","1/(-3)","-1/7","7+(3*5)-(8+20/2)","4-(4-3*5+(2*4)+100)/10"};
		for(int i=0;i<strs.length;i++){
			BigDecimal result = new CalculateString().calculateString(strs[i]);
			System.out.println(result.toString());
		}
		
	}

}

自己写的stack

package graph;

public class Stack<T> {
	public StackNode<T> stackTop;
	public int count;
	public void push(T info) {
		StackNode<T> node = new StackNode<T>();
		node.info = info;
		node.link = stackTop;
		stackTop = node;
		count++;
	} 
	
	public void pop() {
		if(stackTop == null) {
			System.out.println("null stack");
		} else {
			stackTop = stackTop.link;
			count--;
		}

	}
	
	public boolean isEmpty() {
		return count == 0;
	}
	
	public T top() {
		if(stackTop == null) {
			return null;
		}
		return stackTop.info;
	}
	
	public String toString(){
		Stack<T> other = new Stack<T>();
		while(count != 0){
			T top = top();
			pop();
			other.push(top);
		}
		StringBuffer buf = new StringBuffer();
		while(other.count !=0){
			buf.append(other.top());
			other.pop();
		}
		return buf.toString();
	}

}

stack节点

package graph;

public class StackNode<T> {
	public StackNode<T> link;
	public T info;
}

懒得copy的话下载附件

评论

5 楼 only_xxp 2010-08-19  

学习!!!

4 楼 mingjian01 2010-08-18  

如果我只想将一个中缀表达式完整转为后缀表达式，不想中间有计算结果，程序应该怎样写

3 楼 dogstar 2008-04-25  

龙书一本.

2 楼 leon_a 2008-04-24  

引用

我想说，如果你看了 编译原理，会有更大的收获。
努力!

最近也想往编译原理那方面研究..
有什么好书推荐吗?

1 楼 yananay 2008-04-24  

我想说，如果你看了 编译原理，会有更大的收获。
努力!