package lang;
import java.util.Stack;
/**
* @author wanqilin
* @date 2019/6/14
* @description
一次抽象语法树(AST)的练习,进行四则运算的分析和运算
方法很简单,倒序搜索字符串中优先级最低的运算符,将该运算符提出来作为父节点,两边的字符串作为子节点
若没有搜索到操作符,那么该节点为数字
接着对子节点也进行相同的操作,这样我们能得到一个抽象语法树
其中数的节点分为操作符和数字,而数的root节点一定是操作符
我们对该数进行前序遍历,最终计算出返回值
ComputeUnit有两个还未完善的地方,一是valueOf方法还未支持浮点数
另外是Operator::compute 同样为支持浮点数
*/
public class ComputeUnit {
public static void main(String[] args) {
ComputeUnit compute = new ComputeUnit();
System.out.println(compute.compute("(5 + 11 + 485 / 15 + 46 * (15 + 20 )- 156 - 60 * 20)"));
System.out.println((5 + 11 + 485 / 15 + 46 * (15 + 20 )- 156 - 60 * 20));
}
public String compute(String str){
Stack<Node> s = new Stack<>();
Node head = new Node(0,str.length() - 1);
s.push(head);
while (!s.isEmpty()){
Node n = s.pop();
clearBracketOutSideAndSpace(n,str);
int bracketCnt = 0;
int op = 0,opPriority = Integer.MAX_VALUE;
boolean isOpLast = false;
for (int i = n.ep; i >= n.sp; i--) {
char c = str.charAt(i);
if (c == ')') bracketCnt ++;
else if (c == '('){
bracketCnt--;
if (bracketCnt < 0) return "err1";
}
if (bracketCnt == 0){
switch (c){
case ' ':
break;
default:
if (Operate.isOperate(c)){
Operate operate = Operate.valueOf(c);
if (isOpLast && operate.priority == 1){
return "err2";
}
isOpLast = true;
if (opPriority > operate.priority){
opPriority = operate.priority;
op = i;
}
}else isOpLast = false;
}
}
}
if (bracketCnt > 0) return "err3";
if (opPriority == Integer.MAX_VALUE){
Number val = valueOf(n,str);
if (val == null) return "err4";
NumberNode tmp = new NumberNode(n.parent,n.left,n.right,n.sp,n.ep);
tmp.number = val;
if (n.parent == null) head = tmp;
else{
if (n.parent.left == n) n.parent.left = tmp;
else n.parent.right = tmp;
}
continue;
}
OperatorNode operatorNode = new OperatorNode(n.parent,n.left,n.right,op,op);
operatorNode.operate = Operate.valueOf(str.charAt(op));
if (n.parent == null) head = operatorNode;
else{
if (n.parent.left == n) n.parent.left = operatorNode;
else n.parent.right = operatorNode;
}
Node left = new Node(operatorNode,null,null,n.sp,op - 1),right = new Node(operatorNode,null,null,op + 1,n.ep);
operatorNode.left = left;operatorNode.right = right;
s.push(left);s.push(right);
}
return computeNode(head);
}
private void clearBracketOutSideAndSpace(Node n, String str) {
clearBracketOutSide(n,str);
int si,ei;
for (si = n.sp;si < n.ep && str.charAt(si) == ' ';si++);
for (ei = n.ep;ei > n.sp && str.charAt(ei) == ' ';ei--);
n.sp = si;n.ep = ei;
}
private String computeNode(Node head) {
Stack<RecInfo> s = new Stack<>();
s.push(new RecInfo(head,1));
while (!s.isEmpty()){
RecInfo rec = s.pop();
switch (rec.state){
case 1:
if (rec.cur instanceof NumberNode){
rec.state = 3;
s.push(rec);
}else{
rec.state++;
s.push(rec);
s.push(new RecInfo(rec.cur.left,1));
}
break;
case 2:
rec.state++;
s.push(rec);
s.push(new RecInfo(rec.cur.right,1));
break;
case 3:
Number res = null;
if (rec.cur instanceof NumberNode){
res = ((NumberNode) rec.cur).number;
}else{
res = ((OperatorNode) rec.cur).operate.compute(rec.left,rec.right);
}
if (s.isEmpty()){
return res.toString();
}
if (s.peek().cur.left == rec.cur) s.peek().left = res;
else s.peek().right = res;
break;
}
}
return "err10";
}
private Number valueOf(Node n, String str) {
return Integer.valueOf(str.substring(n.sp,n.ep+1));
}
private void clearBracketOutSide(Node n, String str) {
int sp = n.sp,ep = n.ep,si = -1,ei = -1;
for (int i = sp; i < ep; i++) {
char c = str.charAt(i);
if (c == '(') si = i;
else if (c != ' ') break;
}
for (int i = ep; i > sp; i--) {
char c = str.charAt(i);
if (c == ')') ei = i;
else if (c != ' ') break;
}
if (ei != -1 && si != -1){
n.sp = si + 1;
n.ep = ei - 1;
}
}
}
class Node{
Node parent,left,right;
int sp,ep; // start point , end point
public Node(int sp, int ep) {
this.sp = sp;
this.ep = ep;
}
public Node(Node parent, Node left, Node right, int sp, int ep) {
this.parent = parent;
this.left = left;
this.right = right;
this.sp = sp;
this.ep = ep;
}
}
class OperatorNode extends Node{
Operate operate;
public OperatorNode(Node parent, Node left, Node right, int sp, int ep) {
super(parent, left, right, sp, ep);
}
}
class NumberNode extends Node{
Number number;
public NumberNode(Node parent, Node left, Node right, int sp, int ep) {
super(parent, left, right, sp, ep);
}
}
enum Operate{
add(1),sub(1),mul(2),div(2),none(0);
int priority;
Operate(int priority){
this.priority = priority;
}
static Operate valueOf(char ch){
switch (ch){
case '+':
return add;
case '-':
return sub;
case '*':
return mul;
case '/':
return div;
default:
return none;
}
}
Number compute(Number n1,Number n2){
switch (this){
case add:
return (Integer)n1 + (Integer)n2;
case sub:
return (Integer)n1 - (Integer)n2;
case mul:
return (Integer)n1 * (Integer)n2;
case div:
return (Integer)n1 / (Integer)n2;
}
return null;
}
static boolean isOperate(char ch){
return valueOf(ch) != none;
}
}
//recursion information
class RecInfo{
Node cur;
int state;// 1:left 2: right 3: mid
Number left,right;
public RecInfo(Node cur, int state) {
this.cur = cur;
this.state = state;
}
}
网友评论