算式类型字符串表达式读取并计算出结果(简单四则运算)--后缀表达式计算

package com.zpl.suanfa;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 用于界面简单的四则运算字符串类型的表达式
 * 
 * @author zhangpengliang
 * 
 *         算法知识：后缀表达式 a+b*c+(d*e+f)*g
 *         <p>
 *         是正常的表达式，我们要将这个转换成后缀表达式：abc*+de*f+g*+ <br>
 *         1、当读到一个操作数的时候直接输出，操作符不能立即输出，要放到栈中，当遇到"("时也要推入到栈中<br>
 *         2、当遇到")"时，就将栈元素依次弹出，并输出，直到弹出的符号是一个"(",就直接弹出"(",右括号就不能再推入栈中了
 *         3、当遇到其他符号如"+","*","("等时，我们从栈中弹出栈元素并输出直到发现优先级更低的元素为止<br>
 *         如果是同级的，比如"+"与"-"和"+"都是同级。也要弹出输出，虽然"("的优先级很高，但是只有在处理")"才可以弹出但不输出
 *         4、第三步弹出输出完后，需要将这个比较的元素压到栈中 <br>
 *         5、如何计算abc*+de*f+g*+<br>
 *         先将a b 压到栈中，然后遇到操作数就压入栈中，遇到操作符就将栈中的最顶的两位b c与操作符处理，b*c=v;然后再将v压入 <br>
 *         栈中，依次类推
 * 
 * 
 * 
 * 
 *
 */

public class HouZhuiExpression {
	private char[] chs = { '+', '-', '*', '/', '(', ')' };

	/**
	 * 将字符串表达式转换成一个list表，操作数与操作符分开
	 * 
	 * @param exp
	 * @return
	 */
	private List<String> expressionToHouZhuiExpression(String exp) {

		List<String> list = new ArrayList<String>();
		char[] str = exp.toCharArray();
		int j = 0;
		for (int i = 0; i < str.length; i++) {
			if (ishave(str[i])) {
				String res = exp.substring(j, i);
				j = i + 1;
				if (!res.equals("") && res != null)
					list.add(res);
				list.add(String.valueOf(str[i]));
			} else if (j < str.length && i == str.length - 1) {
				String res = exp.substring(j, i + 1);
				j = i;
				list.add(res);
			}
		}

		return list;

	}

	/**
	 * 后缀表达式
	 * 
	 * @param list
	 * @return
	 */
	private List<String> List2HouZhuiExpr(List<String> list) {
		String exp = "";
		List<String> value = new ArrayList<String>();
		Stack<String> stack = new Stack<String>();
		for (String str : list) {
			if (ishave(str)) {
				if (stack.isEmpty())
					stack.push(str);
				else {
					String a = cc(stack, str);
					exp = exp + a;
					if (!a.equals("")) {
						value.addAll(expressionToHouZhuiExpression(a));
					}

				}
			} else {
				exp = exp + str;
				value.add(str);
			}
		}
		if (!stack.isEmpty()) {
			for (int i = stack.size() - 1; i >= 0; i--) {
				exp = exp + stack.get(i);
				value.add(stack.get(i));
			}
		}
		return value;
	}

	/**
	 * 递归逻辑
	 * 
	 * @param stack
	 * @param str
	 * @return
	 */
	private String cc(Stack<String> stack, String str) {
		String a = "";

		if (stack.isEmpty()) {
			stack.push(str);
			return a;
		}
		String stck = stack.peek();
		if (isPop(stck, str)) {
			if (stck.equals("(")) {
				stack.pop();
				return a;
			} else {
				stack.pop();
				a = stck;
				a = a + cc(stack, str);
			}
		} else {
			stack.push(str);
		}
		return a;
	}

	/**
	 * 判断该操作符是否要弹出
	 * 
	 * @param stck
	 * @param s
	 * @return
	 */
	private boolean isPop(String stck, String s) {
		boolean flag = false;
		if (s.equals("+") || s.equals("-")) {
			if (stck.equals("+") || stck.equals("-") || stck.equals("*") || stck.equals("/")) {
				flag = true;
			}
		} else if (s.equals("*") || s.equals("/")) {
			flag = false;
		} else if (s.equals("(")) {
			flag = false;
		} else if (s.equals(")")) {
			flag = true;
		}
		return flag;

	}

	/**
	 * 判断字符是否为操作符
	 * 
	 * @param ch
	 * @return
	 */
	private boolean ishave(char ch) {
		boolean flag = false;
		for (int i = 0; i < chs.length; i++) {
			if (chs[i] == ch) {
				flag = true;
				break;
			}
		}
		return flag;
	}

	/**
	 * 判断字符串是否在这些符号中
	 * 
	 * @param ch
	 * @return
	 */
	private boolean ishave(String ch) {
		boolean flag = false;
		for (int i = 0; i < chs.length; i++) {
			if (String.valueOf(chs[i]).equals(ch)) {
				flag = true;
				break;
			}
		}
		return flag;
	}

	/**
	 * 开始计算
	 * 
	 * @param value
	 * @return
	 */
	private String caculate(List<String> value) {
		Stack<String> s = new Stack<String>();
		s.push(value.get(0));
		s.push(value.get(1));
		for (int i = 2; i < value.size(); i++) {
			String key = value.get(i);
			if (ishave(key)) {
				int a = Integer.valueOf(s.pop());
				int b = Integer.valueOf(s.pop());
				int res = sum(b, a, key);
				s.push(String.valueOf(res));
			} else {
				s.push(key);
			}
		}
		if (s.isEmpty()) {
			return "0";
		} else {
			String res = s.pop();
			return res;
		}
	}

	private int sum(int a, int b, String key) {
		if (key.equals("*")) {
			return a * b;
		} else if (key.equals("/")) {
			return a / b;
		} else if (key.equals("+")) {
			return a + b;
		} else if (key.equals("-")) {
			return a - b;
		} else
			return 0;
	}

	public static void main(String[] args) {
		HouZhuiExpression hze = new HouZhuiExpression();
		// String exp = "a+b*c+(d*e+f)*g";
		String exp = "(6/3+6*2)+9";
		List<String> list = hze.expressionToHouZhuiExpression(exp);

		List<String> b = hze.List2HouZhuiExpr(list);
		String ee = hze.caculate(b);
		System.out.println(ee);

	}

}
package com.zpl.suanfa;

import java.util.Array