transformmodel.java

从正则表达式到NFA的JAVA实现代码

 package reg2nfa;

import java.util.Stack;
import java.awt.Point;
import java.awt.Rectangle;
import java.util.LinkedList;

public class TransformModel implements Constants {
  String[] regExp;           //正则表达式的分解串
  Graph transformGraph;      //图形结构,用于存放结点和边
  GraphNode[] node;
  private int temp;
  private Stack identifyStack;       //栈结构,用于存放标识符
  private Stack operatorStack;       //栈结构,用于存入运算符
  private Stack boundsStack;         //存入图在视图中的范围
  private Stack graphStack;          //存放图的结点集
  private int[] set1, set2;
  private Point p1, p2;
  private Rectangle bounds1, bounds2;
  private LinkedList specialEdgeList;       //存放特殊边的链表

  public TransformModel() {

  }

  public boolean setRegExpression(String exp) {
    //设置正则表达式的字符串集形式
    int n = 0;
    if(canSplit(exp)) regExp = splitExp(exp);
    else return false;

    for(int i = 0; i < regExp.length; i++)
      if(!regExp[i].equals("") && regExp[i].compareTo("(") != 0
          && regExp[i].compareTo(")") != 0)  n++;
    transformGraph = new Graph(2*n);
    node = new GraphNode[2*n];

    for(int i = 0; i < 2*n; i++) {
      node[i] = new GraphNode();
    }

    return true;
  }

  private boolean canSplit(String exp) {
    //exp是否可以分解
    int n1 = 0, n2 = 0, n3 = 0;
    for(int i = 0; i < exp.length(); i++) {
      if (exp.charAt(i) == '\'') n1++;
      if(exp.charAt(i) == '(') n2++;
      if(exp.charAt(i) == ')') n3++;
    }
    return (n1%2 == 0 && n2 == n3);
  }

  private String[] splitExp(String exp) {
    //把字符串按意愿分解成字符串集
    char ch;
    int id = 0;
    int n = exp.length();
    String[] expSet = new String[n+1];
    StringBuffer buf;

    for(int i = 0; i < n + 1; i++)
      expSet[i] = "";

    for(int i = 0; i < n; i++) {
      ch = exp.charAt(i);
      if (ch == '\'') {   //可以由''来决定一个串
        buf = new StringBuffer();
        ch = exp.charAt(++i);
        while (ch != '\'') {
        buf.append(ch);
        ch = exp.charAt(++i);
        }
        expSet[id++] = new String(buf);
      }
      else expSet[id++] = String.valueOf(ch); //也可以由单个
                                                 //字符构成
    }

    return expSet;
  }

  public Graph getGraph() {
    return transformGraph;
  }

  public boolean createNFA() {
    //创建非确定有穷自动机
    identifyStack = new Stack();
    operatorStack = new Stack();
    boundsStack = new Stack();
    graphStack = new Stack();
    specialEdgeList = new LinkedList();

    temp = 0;
    int n = regExp.length;
    //int[] graphSet = new int[2*n];
    char ch;        //从运算栈得到的字符

    int i = 0;
    while(regExp[i] != "") {
      if(!isOperator(regExp[i])) { //如是标识符...
        GraphNode n1 = node[temp++];
        GraphNode n2 = node[temp++];
        basicOperate(n1, n2, n, i);
        if(regExp[i+1] != "" && (!isOperator(regExp[i+1]) || regExp[i+1].equals("(")))
          operatorStack.push(new Character('^'));

      }

      else if(isOperator(regExp[i])) { //如是运算符...
        ch = regExp[i].charAt(0); //为了方便处理,把字符串转换成字符

        switch(ch) {
          case '*':      //*的优先级较高, 故先计算
            if(identifyStack.empty())
              return false;     //标识符栈为空而运算符栈不为空,故表达式错误
            repeatOperate();
            if(regExp[i+1] != "" && (!isOperator(regExp[i+1]) || regExp[i+1].equals("(")))
              operatorStack.push(new Character('^'));
            break;

          case '|':      //可以进行两种运算^和|
            if(identifyStack.empty())
              return false;     //标识符栈为空而运算符栈不为空,故表达式错误
            if(!operatorStack.isEmpty()) {
              ch = ((Character)operatorStack.peek()).charValue();
              while(ch != '(') {
                ch = ((Character)operatorStack.pop()).charValue();;
                p2 = (Point)identifyStack.pop();
                p1 = (Point)identifyStack.pop();
                bounds2 = (Rectangle)boundsStack.pop();
                bounds1 = (Rectangle)boundsStack.pop();
                set2 = (int[])graphStack.pop();
                set1 = (int[])graphStack.pop();

                switch(ch) {
                  case '|':
                    choiceOperate();
                    break;

                  case '^':
                    appositeOperate();
                    break;
                }
                if(!operatorStack.isEmpty())
                  ch = ((Character)operatorStack.peek()).charValue();
                else break;
              }
            }
            operatorStack.push(new Character('|'));
            break;

          case '^':       //进行一种运算^
            if(identifyStack.empty())
              return false;     //标识符栈为空而运算符栈不为空,故表达式错误
            if(!operatorStack.isEmpty()) {
              ch = ((Character)operatorStack.peek()).charValue();
              if(ch == '^') {
                p2 = (Point) identifyStack.pop();
                p1 = (Point) identifyStack.pop();
                bounds2 = (Rectangle) boundsStack.pop();
                bounds1 = (Rectangle) boundsStack.pop();
                set2 = (int[]) graphStack.pop();
                set1 = (int[]) graphStack.pop();

                ch = ( (Character) operatorStack.peek()).charValue();
                if(ch == '^')
                appositeOperate();
              }
              if(!operatorStack.isEmpty())
                  ch = ((Character)operatorStack.peek()).charValue();
                else break;

            }
            operatorStack.push(new Character('^'));
            break;

          case '(':         //直接进入运算栈
            operatorStack.add(new Character('('));
            break;

          case ')':         //计算在括号内的值
            if(identifyStack.empty())
              return false;     //标识符栈为空而运算符栈不为空,故表达式错误
            ch = ((Character)operatorStack.pop()).charValue();
            while(ch != '(') {
              p2 = (Point)identifyStack.pop();
              p1 = (Point)identifyStack.pop();
              bounds2 = (Rectangle)boundsStack.pop();
              bounds1 = (Rectangle)boundsStack.pop();
              set2 = (int[])graphStack.pop();
              set1 = (int[])graphStack.pop();

              switch(ch) {
                case '^':
                  appositeOperate();
                  break;
                case '|':
                  choiceOperate();
                  break;
              }
              ch = ((Character)operatorStack.pop()).charValue();
            }
            if(regExp[i+1] != "" && (!isOperator(regExp[i+1]) || regExp[i+1].equals("(")))
              operatorStack.push(new Character('^'));
            break;
            default: break;
        }
      }
      i++;
    }

    while(!operatorStack.isEmpty()) {
      ch = ((Character)operatorStack.pop()).charValue();
      p2 = (Point)identifyStack.pop();
      p1 = (Point)identifyStack.pop();
      bounds2 = (Rectangle)boundsStack.pop();
      bounds1 = (Rectangle)boundsStack.pop();
      set2 = (int[])graphStack.pop();
      set1 = (int[])graphStack.pop();

      switch(ch) {
        case '^':
          appositeOperate();
          break;

        case '|':
          choiceOperate();
          break;
      }
    }

    return true;
  }


  private void basicOperate(GraphNode n1, GraphNode n2, int n, int i) {
    //处理基本正则表达式
    int[] graphSet = new int[2*n];
    for(int loop = 0; loop < 2*n; loop++) {
      graphSet[loop] = -1;       //将要放入图的结点集栈中
    }

    //设置结点在视图上的初始值
    n1.setPosition(new Point(-2*RADIUS, 0));
    n2.setPosition(new Point(2*RADIUS, 0));

    transformGraph.setStart(n1);
    transformGraph.setEnd(n2);
    transformGraph.addEdge(n1, n2, regExp[i]);
    identifyStack.push(new Point(n1.getID(), n2.getID()));
    //把当前边的范围压入栈
    boundsStack.push(new Rectangle(-3*RADIUS, -RADIUS,
                     6*RADIUS, 2*RADIUS));
    //把边集压入栈, 不为-1的表示所对应的结点存在
    graphSet[n1.getID()] = n1.getID();
    graphSet[n2.getID()] = n2.getID();
    graphStack.push(graphSet);
  }

  private void repeatOperate() {
    //重复
    Point p = (Point)identifyStack.pop();  //标识符栈出栈
    Rectangle bounds = (Rectangle)boundsStack.pop();  //范围栈出栈
    int[] set = (int[])graphStack.pop();
    EdgeLink special;

    GraphNode n1 = node[p.x],
        n2 = node[p.y],
        n3 = node[temp++],
        n4 = node[temp++];
    //设置n3, n4在视图中的初始位置
    n3.setPosition(new Point(n1.getPosition().x - 4*RADIUS,
                             n1.getPosition().y));
    n4.setPosition(new Point(n2.getPosition().x + 4*RADIUS,
                             n2.getPosition().y));

    set[n3.getID()] = n3.getID();
    set[n4.getID()] = n4.getID();

    transformGraph.setStart(n3);
    transformGraph.setEnd(n4);
    transformGraph.addRepeatEdge(n1, n2, n3, n4);
    identifyStack.push(new Point(n3.getID(), n4.getID()));
    boundsStack.push(new Rectangle(n3.getPosition().x - RADIUS,
                                   bounds.y - 2*RADIUS, bounds.width + 8*RADIUS,
                                   bounds.height + 4*RADIUS));
    graphStack.push(set);
    special = new EdgeLink(n2, n1);
    specialEdgeList.add(new SpecialEdge(special, (Rectangle)boundsStack.peek()));
    special = new EdgeLink(n3, n4);
    specialEdgeList.add(new SpecialEdge(special, (Rectangle)boundsStack.peek()));
  }

  private void choiceOperate() {
    //在各项中选择
    int offset;
    offset = -(bounds1.height + bounds1.y + RADIUS);
    moveY(set1, offset);
    offset = -bounds2.y + RADIUS;
    moveY(set2, offset);

    GraphNode n3 = node[temp++];
    GraphNode n4 = node[temp++];
    transformGraph.setStart(n3);
    transformGraph.setEnd(n4);
    transformGraph.addChoiceEdge(node[p2.x], node[p2.y],
                                 node[p1.x], node[p1.y],
                                 n3, n4);
    int width = Math.max(bounds1.width, bounds2.width);
    n3.setPosition(new Point(-width/2 - 3*RADIUS, 0));
    n4.setPosition(new Point(width/2 + 3*RADIUS, 0));

    int[] total = new int[set1.length];
    for(int loop = 0; loop < total.length; loop++) {
      total[loop] = set1[loop] + set2[loop] + 1;
    }
    total[n3.getID()] = n3.getID();
    total[n4.getID()] = n4.getID();

    identifyStack.push(new Point(n3.getID(), n4.getID()));
    boundsStack.push(new Rectangle(n3.getPosition().x - RADIUS, -bounds1.height - RADIUS,
                                   width + 8*RADIUS, bounds1.height + bounds2.height + 2*RADIUS));
    graphStack.push(total);
  }

  private void appositeOperate() {
    //并置
    int offset;
    offset = -bounds1.width/2 - RADIUS;
    moveX(set1, offset);
    offset = bounds2.width/2 + RADIUS;
    moveX(set2, offset);

    int[] total = new int[set1.length];
    for(int loop = 0; loop < total.length; loop++) {
      total[loop] = set1[loop] + set2[loop] + 1;
    }

    int height = Math.max(bounds1.height, bounds2.height);
    transformGraph.setStart(node[p1.x]);
    transformGraph.setEnd(node[p2.y]);
    transformGraph.addAppositiveEdge(node[p1.y], node[p2.x]);
    identifyStack.push(new Point(p1.x, p2.y));
    graphStack.push(total);

    Rectangle bounds = new Rectangle(-bounds1.width - RADIUS, Math.min(bounds1.y, bounds2.y),
                                   bounds1.width + bounds2.width + 2*RADIUS, height);
    offset = -bounds.x - bounds.width/2;
    moveX(total, offset);
    bounds.x += offset;
    boundsStack.push(bounds);
  }

  private void moveX(int[] set, int offset) {
    for(int i = 0; i < set.length; i++)
      if(set[i] != -1) {
        Point p = node[set[i]].getPosition();
        node[set[i]].setPosition(new Point(p.x + offset, p.y));
      }
  }

  private void moveY(int[] set, int offset) {
    for(int i = 0; i < set.length; i++)
      if(set[i] != -1) {
        Point p = node[set[i]].getPosition();
        node[set[i]].setPosition(new Point(p.x, p.y + offset));
      }
  }

  public Rectangle getBounds() {
    //返回图在视图中的初始位置
    return (Rectangle)boundsStack.peek();
  }

  public LinkedList getSpecialEdge() {
    return specialEdgeList;
  }

  private boolean isOperator(String str) {
    //判断是否运算符(包括())
    if(str.compareTo("*") == 0 | str.compareTo("|") == 0
       | str.compareTo("(") == 0 | str.compareTo(")") == 0)
      return true;
    return false;
  }
}