java实现四则混合运算

  最近在看数据结构。想要实现四则混合运算。用栈来实现。

  去网上看了好些代码（想偷懒来着）结果代码都不全。思路不清晰。

  看的难受，最后觉得还是自己写吧。学习嘛，偷懒不得。

  栈的本质就是个线性表。结构就是个后进先出的胡同。只能操作线性表表尾元素的插入和删除。

  

  下面是对栈的实现。这些基本是照搬别人的。

package stack;

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

/**
 * 栈的实现，先进后出。
 */
public class Stack {
	// 初始化数组
	public String[] stackArr = new String[16];
	// 栈的顶部
	int top = -1;

	// 出栈操作
	public String pop() {
		return stackArr[top--];
	}

	// 进栈操作
	public void push(String c) {
		// 原数组满了，就扩容1.5倍
		if (isFull()) {
			resize();
		}
		stackArr[++top] = c;
	}
	
	// 清空栈
    public void clear() {     
    	stackArr = null;     
    	top = -1;     
    }   

    // 栈的元素个数
    public int length() {     
        return top + 1;     
    }   
	// 判断栈是否为空
	public boolean isEmpty() {
		return top == -1;
	}

	// 判断栈是否已满
	public boolean isFull() {
		return top == stackArr.length - 1;
	}

	// 取栈顶元素
	public String peek() {
		return stackArr[top];
	}

	/**
	 * 数组扩容，1.5倍长度
	 */
	private void resize() {
		String[] temp = new String[stackArr.length * 3 / 2 + 1];
		for (int i = 0; i < stackArr.length; i++) {
			temp[i] = stackArr[i];
		}
		stackArr = temp;
	}

	public void print (){
		for (int i = 0; i <= top; i++) {
			 System.out.print(stackArr[i]);
		}
	}

}

    

   这里需要讲一下四则混合运算的步骤，

   先科普一下后缀表达式：它是波兰的一个哥们想出来的。名字太长不好记，就被后人称为逆波兰表达式了。

   中缀表达式：9+ (3-1) * 3+10/ 2

   后缀表达式：931一3 * +102/+

 

   1，将中缀表达式转化为后缀表达式（逆波兰表达式Reverse Polish Notation）

            规则:从左到右遍历表达式的每个数字和符号,遇到是数字就进栈,遇到是符号,就将处于栈顶两个数字出栈，进行运算,运算结果进栈, 一直到最终获得结果

    2，将后缀表达式进行运算得出结果

           规则:从左到右遍历中缀表达式的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分 i 若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出 , 并将当前符号进栈,一直 到最终输出后缀表达式为止。

 

  下面是我自己对四则混合运算的实现。写的时候小坑比较多。你们自己写过就知道了。

package stack;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.List;

import org.apache.commons.lang.StringUtils;

/**
 * 四则混合运算<br/>
 * 支持小数运算，支持带负数运算。
 */
public class Operation {
	// 栈
	static Stack stack = new Stack();

	public static void main(String[] args) {
//		 String jisuan = "-9*(9+2+(-1)+7)";
		 String jisuan = "-9+（9+(3-1）*3.13+1.2/2+(7-2)）";
//		String jisuan = "9+(1-3）*3+10/2";

		// 做处理：剔除空格，将中文的括号统一替换成英文的
		jisuan = replaceStr(jisuan);
		
		// 计算公式字符串处理成集合
		List<String> arry = stringToList(jisuan);

		// 中缀表达式处理为后缀表达式
		List<String> end = CenToEnd(arry);

		// 计算结果
		String result = Opera(end);
		System.out.println(result);
		
		
		// 写#的是有值就写值，没值就不写	DecimalFormat df=new DecimalFormat("#.000");
		// 写0的是有值就写值，没值就写0	DecimalFormat df=new DecimalFormat("0.000");
		double d = Double.parseDouble(result);
		DecimalFormat df=new DecimalFormat("0.00");
		String d2 = df.format(d);
		System.out.println(d2);

		// 开始计算数值

	}

	/**
	 * 计算结果<br/>
	 * 是数字，就进栈，<br/>
	 * 是字符，就把栈顶值取出，根据字符进行运算，然后再放入到栈中，一直到把集合遍历结束为止
	 * @param end 后缀运算表达式List集合
	 * @return 运算结果
	 */
	private static String Opera(List<String> end) {

		double first = 0;
		double second = 0;

		for (String str : end) {
			try {
				// 如果是数字，将不会抛异常，如果不是，那么将会走catch部分。
				Double.parseDouble(str);
				stack.push(str);
			} catch (Exception e) {
				double result = 0;
				// 不是数字

				// 如果栈中是1，2，3 符号是 - ，原来的公式是 2-3=-1
				// second = 3, first = 2 
				// 位置颠倒后，就变成了second = 3, first = 2 公式就变成了3-2=1
				// 所以下面两行代码顺序不能颠倒
				second = Double.parseDouble(stack.pop());
				first = Double.parseDouble(stack.pop());

				// 计算
				if (str.equals("+")) {
					result = first + second;
				} else if (str.equals("-")) {
					result = first - second;
				} else if (str.equals("*")) {
					result = first * second;
				} else {// 除
					result = first / second;
				}

				// 将每次运算完的结果再次放到栈顶
				stack.push(result + "");
			}

		}
		// 取出栈顶的值，也就是最后的运算结果
		return stack.peek();
	}

	/**
	 * 容错处理：处理空格，中文括号。
	 * 
	 * @param str 输入的运算表达式字符串
	 * @return
	 */
	private static String replaceStr(String str) {

		str = str.replace(" ", "");
		str = str.replace("（", "(");
		str = str.replace("）", ")");
		str = str.replace("。", ".");
		String[] strArr = str.split("=");
		return strArr[0];
	}

	/**
	 * 中缀表达式处理为后缀表达式<br/>
	 * 遍历中缀表达式，是数字，就添加到后缀表达式的list中。<br/>
	 * 				是符号，就判断与栈顶符号的优先级。是右括号“)”或者优先级低于栈顶符号，<br/>
	 * 				栈顶元素就依次输出到后缀表达式的list，并将当前符号入栈。
	 * @param arry 中缀运算表达式List集合
	 * @return	后缀表达式list集合
	 */
	private static List<String> CenToEnd(List<String> arry) {
		// 后缀表达式集合
		List<String> end = new ArrayList<String>();
		for (String c : arry) {

			// 是数字就添加到
			if (StringUtils.isNumeric(c)) {
				end.add(c);
				continue;
			}

			// 判断和栈顶符号的优先级
			if (isPriority(c)) {
				stack.push(c);
			} else {
				// 当前值C优先级低于栈顶，并且C是右括号“)”
				// 栈顶符号依次出栈。取出来的栈顶值加入list
				if (c.equals(")")) {
					while (!stack.isEmpty()) {
						// 栈顶出栈
						String topValue = stack.pop();
						if (topValue.equals("(")) {
							break;
						}
						// 栈顶值加入后缀表达式集合
						end.add(topValue);
					}
				} else {
					// 当前值C优先级低于栈顶，栈顶符号出栈，C进栈。取出来的栈顶值加入list					
					// 栈顶出栈
					String topValue = stack.pop();
					// 栈顶值加入后缀表达式集合
					end.add(topValue);
					stack.push(c);
				}
			}

		}

		// 添加最后栈中剩下的元素
		while (!stack.isEmpty()) {
			end.add(stack.pop());
		}
		return end;
	}

	/**
	 * 判断c和栈顶符号的优先级：右括号或者优先级低于栈顶符号，栈顶符号以此出栈输出，并将当前符号进栈，<br/>
	 * 
	 * @param c
	 * @return true:当前值C优先栈顶，C进栈. <br/>
	 *         false：当前值C低于栈顶，栈顶符号出栈，C进栈。
	 */
	public static boolean isPriority(String c) {

		// 空栈，c进栈
		if (stack.isEmpty()) {
			return true;
		}

		// 右括号，栈顶依次出栈，直到匹配到最近的左括号（
		if (c.equals(")")) {
			return false;
		}

		// 左括号（ 一律进栈。不比较优先级 
		if (c.equals("(")) {
			return true;
		}

		// 栈顶值
		String topValue = stack.peek() + "";

		// 优先级：左括号（  > （乘 = 除） >（加 = 减）> 右括号）
		if (topValue.equals("+") || topValue.equals("-")) {
			if (c.equals("*") || c.equals("/")) {
				return true;
			} else {
				return false;
			}
		} else {
			if (topValue.equals("/") || topValue.equals("*")) {
				if (c.equals("+") || c.equals("-")) {
					return false;
				} else {
					return true;
				}
			} else {
				// 能走到这里，只剩下（ 了。优先级它最低
				return true;
			}
		}
	}

	/**
	 * 将计算公式字符串变成list，也就是需要使用的中缀表达式的list形式<br/>
	 * 需要处理小数点和负数的情况
	 * @param str
	 * @return 中缀表达式list集合
	 */
	public static List<String> stringToList(String str) {
		// String str = "-9+(3-1)*3+10.5/2+4*5-2";
		char[] arry = str.toCharArray();
		// 字符串缓存
		StringBuilder builder = new StringBuilder();
		// 字符串处理后的集合
		List<String> list = new ArrayList<String>();

		for (int i = 0; i < arry.length; i++) {

			// 是数字就存到缓存中，如果循环的下个元素还是数字，就将其添加到缓存字符串后面。
			// 如果是带小数的数，也要收集完整
			if (StringUtils.isNumeric(arry[i] + "") || ".".equals(arry[i] + "")) {

				// 如果是循环的最后一位，就直接添加到缓存中
				if (i == arry.length - 1) {
					list.add(arry[i] + "");
					continue;// 有没有无所谓，后面的builder添加了元素也没人再用它了。
				}
				builder.append(arry[i]);
				continue;
			} else {
				// 如果<0,就不要向list中添加空了
				// 如果>0,说明上一轮循环结束，已经搜集到了完整的数字。添加到list中
				if (builder.length() > 0) {
					list.add(builder.toString());
				}

				// 当公式最前面有负数时的处理
				// 例如：-9+(3-1）*3+10/2+(7-2)
				if (i == 0 && (arry[i] + "").equals("-")) {
					list.add("0");
					list.add("-");
					continue;
				}
				
				// 如果公式中间带负数时的处理
				// 例如：-9+(-2）*3+10/2+(7-2)
				if((arry[i] + "").equals("-") && list.get(list.size()-1).equals("(")){
					list.add("0");
					list.add("-");
					continue;
				}

				list.add(arry[i] + "");

				// 为下一次循环做准备，清空内容
				builder = new StringBuilder();
			}

		}
		return list;
	}
}