java写的四则运算器

本打算做一个从RE到NFA的转换器，思路已经理清了，但是在动手做的时候，遇到了很多问题，有些技术难点都遗忘了，包括如何定义闭包，如何利用递归来实现。

 

于是回头重新拾起这些技术，边学边思考，做了个四则运算器练练手，为着那个大目标做准备。

 

 

基本的思路是这样的：

 

根据输入的四则运算表达式，生成一棵二叉树，树的根节点是操作符，而子树可能是叶子节点，即数字。也可能是另一个运算表达式。生成树的规则是，对每一个节点产生一个相应的type值，type值越大，就在树的越靠上节点。基本原则是： 数字(10) < 乘除运算(20) < 加减运算(30)。

 

括号被当做是一种特殊的符号，并不会在二叉树上显示出来，相应的，它会影响到在括号内出现符号的type值，每嵌套一层括号，就会将type值减少100, 这样确保了括号内的内容在树的最底层。

 

当二叉树构造好了之后，利用递归，将左树的计算结果与右树的结果，根据根操作符计算出结果。

 

举例：10 

生成树只有一个节点，同时也是根节点，返回值便是根节点值。

 

举例： 10 + 2

首先生成根节点为10，但当读入+时，+的type值比10高，因此上移，并成为新的跟节点，最后加入2，因为2比+type值小，因此作为右子节点。

 

举例： 10 + 2 * 5

当读入*时，*的type值比2大，因此上移，同时又比+的type值小，因此就在+与2之间插入新的节点。

 

举例： 10 + 2 *(2 + 3)

当读入(时，后面所产生的所有Node的type值会相应的-100， 因此括号内的+的type值就会比外面的*小，但是仍然比括号内的数字大，这样保证了在树中，2+3会先执行。当读入)时，offset清零。

 

 

public class Main {

	public static void main(String[] args) {
		String exp = "(10 + 15) * 3 - 20 * 6 /5 - (8 + 14(2- 1))2 + 11(12 - 11)5";
		//String exp = "12";
		Main main = new Main();
		Main.index = 0;
		
		char[] input = main.prepare(exp.toCharArray());
		
		System.out.println(main.cal(input));
	}
	
	/**
	 * Actual calculate method.
	 * @param exp
	 * @return
	 */
	public int cal(char[] exp) {
		Node root = buildTree(exp);
		
		return calculate(root);
	}
	
	/**
	 * Prepare the exp, remove empty space or \n.
	 * Also the method will add losing * in below cases:
	 * 10(3-1)   ---->   10*(3-1)
	 * (3-1)10   ---->   (3-1)*10
	 * 
	 * @param exp
	 * @return
	 */
	public char[] prepare(char[] exp) {
		char[] worklist = new char[exp.length];

		int j = 0;
		for (int i = 0; i < exp.length; i++) {
			char c = exp[i];

			if (c == ' ' || c == '\n') {
				continue;
			} else {
				if (c == '(') { // Handle the abbreviated * for (
					if(j == 0 || isCalculator(worklist[j - 1])) {
						//Do nothing.
					} else {
						worklist[j++] = '*';
					}

					
					worklist[j++] = c;
				} else if (c == ')') {// Handle the abbreviated * for )
					worklist[j++] = c;
					
					while((i == exp.length - 1) || (exp[++i] == ' ')) {
						//Do nothing.
					}
					
					if(isCalculator(exp[i]) || exp[i] == ')') {
						//Do nothing.
					} else {
						worklist[j++] = '*';
					}
					
					i--;
				} else {
					worklist[j++] = c;
				}
			}
		}
		
		char[] result = new char[j];
		
		System.arraycopy(worklist, 0, result, 0, j);
		
		return result;
	}
	
	/**
	 * Check if c is a calculator or not.
	 * @param c
	 * @return
	 */
	private boolean isCalculator(char c) {
		if(c == '+' || c == '-' || c == '*' || c == '/') {
			return true;
		}
		
		return false;
	}
	
	/**
	 * Calculate the tree.
	 * 
	 * @param node
	 * @return
	 */
	private int calculate(Node node) {
		if(node.isLeaf()) return Integer.parseInt(node.value);
		
		if(node.value.equals("+")) {
			return calculate(node.leftChild) + calculate(node.rightChild);
		} else if(node.value.equals("-")) {
			return calculate(node.leftChild) - calculate(node.rightChild);
		} else if(node.value.equals("*")) {
			return calculate(node.leftChild) * calculate(node.rightChild);
		}else {
			return calculate(node.leftChild) / calculate(node.rightChild);
		}
	}
	
	/**
	 * Build a tree like this:
	 * 
	 * 10 * (3 + 5)
	 *  * ------ 10
	 *    -
	 *    ------ +
	 *           -
	 *           ------- 3
	 *           ------- 5 
	 * @param exp
	 * @return
	 */
	private Node buildTree(char[] exp) {
		Node root = null;
		Node working = null;
		
		while(true) {
			Node node = readNext(exp);
			
			if(node == null) break;
			
			if(root == null) {
				root = node;
				working = node;
				
				continue;
			}
			
			if(node.type > working.type) {
				
				Node parent = working.parent;
				boolean isLeft = false;
				while(parent != null && node.type >= parent.type) {
					isLeft = parent.isLeft;
					working = parent;
					parent = parent.parent;
				}
				
				if(parent == null) {
					working.parent = node;
					node.leftChild = working;
					working.isLeft = true;
					
					root = node;
				} else {
					Node tmp = isLeft ? parent.leftChild : parent.rightChild;
					
					if(isLeft) {
						parent.leftChild = node;
					} else {
						parent.rightChild = node;
					}
					node.isLeft = isLeft;
					node.parent = parent;
					tmp.parent = node;
					node.leftChild = tmp;
					tmp.isLeft = true;
				}
			} else {
				working.rightChild = node;
				node.isLeft = false;
				node.parent = working;
			}

			working = node;
		}
		
		return root;
	}
	
	private static int index = 0;
	// Read the next node, it possible to be a number, a calculator or just space.
	private Node readNext(char[] exp) {
		
		if(index >= exp.length) return null;
		
		Node node = new Node();
		
		char c = exp[index++];
		
		if(Character.isDigit(c)) {
			node.type = Node.NUMBER + offset;
			StringBuffer sb = new StringBuffer();
			sb.append(c);
			for(; index < exp.length; index++) {
				char tmp = exp[index];
				if(Character.isDigit(tmp)) {
					sb.append(tmp);
				} else {
					break;
				}
			}
			
			node.value = sb.toString();
		} else if (c == '*' || c == '/') {
			node.type = Node.MUL_DEL + offset;
			node.value = Character.toString(c);
		}else if (c == '+' || c == '-') {
			node.type = Node.PLUS_MINUS + offset;
			node.value = Character.toString(c);
		} else if(c == '(') {
			increaseOffset();
			return readNext(exp);
		}else if(c == ')') {
			decreaseOffset();
			return readNext(exp);
		}
		
		return node;
	}
	
	
	// Every type in the embrace will have to add a offset as their type.
	private static int offset = 0;
	public static void increaseOffset() {
		offset = offset - 100;
	}
	
	public static void decreaseOffset() {
		offset = offset + 100;
	}
	

	/**
	 * Helping class.
	 *
	 */
	class Node {
		private int type = 10;
		
		private Node parent = null;
		
		private Node leftChild = null;
		
		private Node rightChild = null;
		
		private boolean isLeft = false;
		
		private String value = null;
		
		public Node() {
			
		}
		
		public static final int NUMBER = 10;
		public static final int MUL_DEL = 20;
		public static final int PLUS_MINUS = 30;

		public static final int EMBRACE = -100;
		
		public boolean isLeaf() {
			if(leftChild == null && rightChild == null) {
				return true;
			}
			
			return false;
		}

		public int getType() {
			return type;
		}

		public void setType(int type) {
			this.type = type;
		}

		public Node getParent() {
			return parent;
		}

		public void setParent(Node parent) {
			this.parent = parent;
		}

		public Node getLeftChild() {
			return leftChild;
		}

		public void setLeftChild(Node leftChild) {
			this.leftChild = leftChild;
		}

		public Node getRightChild() {
			return rightChild;
		}

		public void setRightChild(Node rightChild) {
			this.rightChild = rightChild;
		}

		public boolean isLeft() {
			return isLeft;
		}

		public void setLeft(boolean isLeft) {
			this.isLeft = isLeft;
		}

		public String getValue() {
			return value;
		}

		public void setValue(String value) {
			this.value = value;
		}
	}
}

 

 

评论

1 楼 mabusyao 2011-08-21  

今天看到另一位仁兄用栈的方式实现，想法也是不错：
http://justsee.iteye.com/blog/1125174