双栈结构_表达式求值

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class MyA {
	
	//定义计算的方法
	static void calcu(Stack data, Stack op) {
		int b = (Integer) data.pop();
		int a = (Integer) data.pop();
		char x = (Character) op.pop();
		if (x == ‘+‘)
			data.push(a + b);
		if (x == ‘-‘)
			data.push(a - b);
		if (x == ‘*‘)
			data.push(a * b);
	}

	public static void main(String[] args) {
		String s = "3*(7-2*3)+5";

		char[] cc = s.toCharArray();
		// 这里假设操作数是1位的，实际可以先词法分析，支持更复杂的操作数。
		// 假设只有乘法、加法、减法，也是为了突出问题的核心逻辑

		// 优先级
		Map map = new HashMap();
		map.put(‘(‘, 0);//左括号优先级为0，最低
		map.put(‘+‘, 1);
		map.put(‘-‘, 1);
		map.put(‘*‘, 2);

		Stack data = new Stack();//操作数栈
		Stack op = new Stack();//操作符栈

		for (int i = 0; i < cc.length; i++) {
			if (cc[i] >= ‘0‘ && cc[i] <= ‘9‘)//判断它是否是数字
				data.push(cc[i] - ‘0‘);//压入到操作数栈中，减去0是为了把字符化为整数
			else if (cc[i] == ‘(‘)//遇到左括号
				op.push(‘(‘);//吧左括号压入运算符栈中
			else if (cc[i] == ‘)‘) {//如果是右括号
				while ((Character) op.peek() != ‘(‘){//栈顶如果不是左括号，Character转换
					calcu(data, op);//进行一次运算
				}
				op.pop();//左括号弹栈
			} else {
				while (op.isEmpty() == false
						&& (Integer) map.get(cc[i]) <= (Integer) map.get(op
								.peek()))//当前运算符优先级和栈顶元素的优先级进行比较
					calcu(data, op);//如果当前低，进行计算
				op.push(cc[i]);
			}
		}

		while (op.isEmpty() == false)
			calcu(data, op);
		System.out.println(data.pop());
	}
}

8

双栈结构_表达式求值,布布扣,bubuko.com

双栈结构_表达式求值

原文：http://blog.csdn.net/u011925500/article/details/20793525