表达式解析器

 今天逛javaEye看到久违的逆波兰式又重出江湖（见 http://www.iteye.com/topic/717341），恰好毕业一年快一个月了，决定写一篇技术BLO纪念一下渐行渐远的大学时光。


这个解析器支持以下几个功能：

1.负数

2.四则运算

 

3.支持变量

3.自定义函数


原理是逆波兰式，结构是设计模式里的解释器模式，调用代码如下：

 

public static void main(String[] args) {
		String exp = "mod(11,3)+2*a*t*t";
		try {
			Node expNode = parse(exp);
			expNode.setVariable("a", 10);
			expNode.setVariable("t", 2);
			if (expNode != null)
				System.out.println(expNode + "=" + expNode.getValue());
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

 

 

一.类结构如下：

 

Node主要有三个方法

interface Node {
 /**
  * 返回表达式
  * @return
  */
 public String toString();

 /**
  * 设置变量值
  * @param var
  * @param value
  */
 public void setVariable(String var, double value);

 /**
  * 返回值
  * @return
  */
 public double getValue();
}

 

OptNode和NumNode分别标识操作符节点和数值节点

OptNode会多一个public int getPriority()方法返回优先级。

 

二.主要的函数有两个

1.解析节点：

    这个方法的功能是解析字符串，根据字符串的内容生成相应的结点

public static Node parse(String exp) throws Exception {// 注册函数
		registerFuns();
		char[] ch = exp.toCharArray();
		Stack<Node> nodes = new Stack<Node>();
		for (int i = 0; i < ch.length;) {
			char c = ch[i];
			if (isSpace(c)) {
				i += 1;
				continue;
			} else if (isNum(nodes, c)) {
				String num = readNum(ch, i);
				nodes.push(value(Double.valueOf(num)));
				i += num.length();
			} else if (isOpt(c)) {
				Node opt = null;
				switch (c) {
				case '+':
					opt = new AndOptNode();
					break;
				case '-':
					opt = new SubOptNode();
					break;
				case '*':
					opt = new MultiOptNode();
					break;
				case '/':
					opt = new DivOptNode();
					break;
				case ',':
					opt = new CommaOptNode();
					break;
				default:
					break;
				}
				if (opt != null) {
					nodes.push(opt);
					i += 1;
				}
			} else if (c == ')') {
				List<Node> nodesInBracket = new ArrayList<Node>();
				Node node = nodes.pop();
				while (!nodes.isEmpty() && !(node instanceof LeftBracket)) {
					nodesInBracket.add(0, node);
					node = nodes.pop();
				}

				BracketNode result = compute(nodesInBracket);
				/*
				 * 如果前一个点是函数，则将其设为函数的参数，否则，则作为一般的节点
				 */
				if (!nodes.isEmpty() && nodes.peek() instanceof FunctionNode) {
					FunctionNode fun = (FunctionNode) nodes.peek();
					fun.setParamNode(result);
				} else {
					nodes.push(result);
				}
				i += 1;
			} else if (c == '(') {
				nodes.push(leftBracket());
				i += 1;
			} else if (isVarStartChar(c)) {
				String indentifier = readIndentifier(ch, i);
				if (isFun(indentifier)) {
					FunctionNode fun = newFun(indentifier);
					nodes.push(fun);
				} else {
					nodes.push(var(indentifier));
				}
				i += indentifier.length();
			}
		}
		List<Node> buf = new ArrayList<Node>();
		while (!nodes.isEmpty()) {
			buf.add(0, nodes.pop());
		}
		if (buf.size() > 0) {
			BracketNode result = compute(buf);
			return result.getNode();
		} else
			return null;
	}

 

2.计算结点

这个方法的作用就是计算一系列不带括号的节点

 

private static BracketNode compute(List<Node> nodes) throws Exception {
		Stack<Node> stack = new Stack<Node>();
		Stack<OptNode> opts = new Stack<OptNode>();
		for (int i = 0; i < nodes.size(); i++) {
			Node node = nodes.get(i);
			if (node instanceof OptNode) {
				OptNode optNode = (OptNode) node;
				if (!opts.isEmpty()) {
					OptNode preNode = opts.peek();
					if (preNode.getPriority() >= optNode.getPriority()) {
						opts.pop();
						merge(stack, preNode);
					}
				}
				opts.push(optNode);
			} else {
				stack.push(node);
			}
		}
		while (!opts.isEmpty()) {
			merge(stack, opts.pop());
		}
		if (stack.size() != 1) {
			throw new Exception("express error");
		}
		return bracket(stack.pop());
	}

 
 3.其他

 

自定函数就是匹配标识符与注册的函数名，如果有，则利用反射生成相应的函数结点，如果没有，则作为普通的变量标识符使用。

可以像这样注册函数

private static void registerFuns() {
		registerFun("mod", ModFunction.class);
		registerFun("sqrt", SqrtFunction.class);
	}

 

 

第一次发这种内容复杂的贴，排版有点乱，注释有点少，将就着看吧。

 

图方便，把类都丢在一个类文件里，具体的代码见附近