表达式的二叉树表示(表达式树转化为二叉树)

package db;

class TNode2 {
	TNode2 left;
	TNode2 right;
	char value = '#';

	@Override
	public String toString() {

		return value + "";
	}
}

public class T2 {
	static int pos = 0;
	// static String str = "1+3*(4-1)+2";
	static String str = "1+1*1";

	// static String str = "1-2";
	public static void main(String[] args) {
		TNode2 r = expression_value();
		print(r);
	}

	static void print(TNode2 r) {
		if (r != null) {
			print(r.left);
			System.out.print(r.value + "");
			print(r.right);
		}
	}

	static TNode2 expression_value() {
		TNode2 e_root = new TNode2();

		TNode2 node3 = e_root;
		TNode2 node = null;
		TNode2 node2 = null;
		TNode2 result = term_value();
		e_root.left = result;
		e_root.right = new TNode2();

		while (true) {
			if (pos >= str.length()) {
				break;
			}
			char op = str.charAt(pos);// 查看输入流中的第一个元素，但不取走
			if (op == ')') {
				pos++;

				TNode2 l = e_root.left;
				if (l.value == '#') {
					e_root = l;
				}
				if (e_root.value == '#') {
					e_root = e_root.left;
				}
				TNode2 ll, rr, p;
				p = e_root;
				while (true) {
					rr = p.right;
					if (rr == null) {
						break;
					}
					if (rr.right == null) {
						break;
					}
					if (rr.right.value == '#') {
						p.right = rr.left;
						break;
					}
					p = rr;
				}
				return e_root;
			} else if (op == '+' || op == '-') {
				TNode2 l = e_root.left;
				if (l.value == '#') {
					e_root = l.left;
					node3 = new TNode2();
					node3.left = e_root;
					node3.right = new TNode2();
					e_root = node3;
				}
				pos++;
				node = node3.right;
				node3.value = op;
				node.value = op;
				node2 = term_value();
				if (pos < str.length()) {
					node.left = node2;
					node3 = node;
					node3.right = new TNode2();
				} else {
					node.value = node2.value;
					node.left = node2.left;
					node.right = node2.right;
				}
			} else {
				if (node != null && node2 != null) {
					node.value = node2.value;
					node.left = node2.left;
					node.right = node2.right;
				}
				break;
			}
		}

		return e_root.value == '#' ? e_root.left : e_root;
	}

	static TNode2 term_value() {
		TNode2 root = new TNode2();
		TNode2 result = factor_value();
		root.left = result;
		root.right = new TNode2();
		TNode2 node3 = root;
		TNode2 node = null;
		TNode2 node2 = null;
		boolean flag = false;
		while (true) {
			if (pos >= str.length()) {
				break;
			}
			char op = str.charAt(pos);
			if (op == '*' || op == '/') {
				flag = true;
				pos++;
				node = node3.right;
				node3.value = op;
				node.value = op;
				node2 = factor_value();
				if (pos < str.length()) {
					node.left = node2;
					node3 = node;
					node3.right = new TNode2();
				} else {
					node.value = node2.value;
					node.left = node2.left;
					node.right = node2.right;
				}
			} else {

				if (node != null && node2 != null) {
					TNode2 n = root, p = root.right;
					while (true) {
						if (p.right.right == null) {
							n.right = p.left;
							break;
						}
						n = p;
						p = p.right;
					}
				}
				break;
			}
		}
		return flag ? root : result;
	}

	static TNode2 factor_value() {
		TNode2 result = null;
		char c = str.charAt(pos);
		if (c == '(') {
			pos++;
			result = expression_value();
			/// pos++;
		} else// 因子本身是一个数字(整个递归的出口)
		{
			pos++;
			TNode2 node = new TNode2();
			node.value = c;
			result = node;
		}
		return result;
	}

}