首页 > 代码库 > 表达式计算器的设计与实现

表达式计算器的设计与实现

一、             字符集定义

1.  <字符> → <数字>│<单界符>│.

2.  <数字> → 0│<非零数字>

3.  <非零数字>→ 1│2│…│9

4.  <单界符> →<运算符>│(│)

5.  <运算符> → +│-│*│/

二、             单词集定义

6.<单词> → <单界符>│<常数>

7.<常数> → <无符号整数>│<无符号浮点数>

8.<无符号整数> →0│<非零整数>

9.<非零整数> → <非零数字> <数字串>

10.<数字串> → <数字> <数字串>│NULL

11.<无符号浮点数> →<无符号整数>. <数字> <数字串>

三、             数据类型定义

12.<类型> → intdouble

四、             表达式定

13.<算术表达式> → <项> + <算术表达式>│<项> - <算术表达式>│<项>

14.<项> → <因子> * <项>│<因子> / <项>│<因子>

15.<因子> → <算数量>│- <因子>

16.<算术量> → <常数>│( <算术表达式> )

 

     E            T        E              E       T     T

<算术表达式> → <项> + <算术表达式>│<算术表达式>-<项>│<项>

 T        F      T      F     T      F

<项> → <因子> * <项>│<因子> / <项>│<因子>

  F         i          F

<因子> → <常数>│- <因子>

 技术分享

核心代码:

(词法分析类Build.java)

  1 package util;
  2 
  3 
  4 
  5 
  6 public class Build {
  7   //下标 
  8   private int i;
  9   
 10   //存储读取的字符
 11   private char ch;
 12   
 13   //将输入自符串转为字符数组
 14   private char[] input_array;
 15   
 16   //截取存储字符串
 17   private String s;
 18   //记录上一次运算符出现的位置
 19   private int lastSingle;
 20   private String input;
 21   public Build(String input){
 22       this.input_array = input.toCharArray();
 23       this.input=input;
 24       ch=input_array[0];
 25       this.i=0;
 26       this.lastSingle=-1;
 27   }
 28   
 29   
 30   
 31   //词法分析函数
 32   public int getsym(){
 33       
 34       
 35       
 36     //i=0时,首字符为小数点,+,-,*,/抛出错误
 37     if(BuildUtils.throwFirstSigleError(ch)){
 38     //将此次非法标识符出现的位置存储到lastSingle
 39     lastSingle=0;
 40     i++;
 41     }
 42     
 43     
 44      while(i<input.length()){//外层循环用于判断是何种别的单词
 45          
 46           ch=input_array[i];
 47           while(ch==‘ ‘||ch==10||ch==13||ch==9){//换行,空格,回车和tab
 48     
 49                   ch=input_array[i++];//取下一个字符到ch
 50          
 51           }
 52           
 53           if(ch>=‘0‘&&ch<=‘9‘){ //检测是否为数字,如果为数字测需要分段存储数字串
 54               if(ch==‘0‘){//如果为0
 55                   i++;
 56                   if(i<input.length())    ch=input_array[i];//取下一个字符到ch
 57                   else{
 58                       BuildUtils.getEndSingle(input, lastSingle, i);break;
 59                   }
 60                   if(ch==‘.‘){//为小数点
 61                       i++;
 62                       if(i<input.length())    ch=input_array[i];    
 63                           else{
 64                                BuildUtils.getEndSingle(input, lastSingle, i);break;
 65                           }//取下一个字符到ch
 66                           if(ch>=‘0‘&&ch<=‘9‘){//取下一个字符到ch//小数点后面的数字
 67                               i++;
 68                               if(i<input.length())    ch=input_array[i];    
 69                               else{
 70                                    BuildUtils.getEndSingle(input, lastSingle, i);break;
 71                               }//取下一个字符到ch//小数点后面的后面
 72                               if(ch>=‘0‘&&ch<=‘9‘){
 73                                   while(ch>=‘0‘&&ch<=‘9‘) {    
 74                                       i++;
 75                                       if(i<input.length())    ch=input_array[i];    
 76                                       else{
 77                                            BuildUtils.getEndSingle(input, lastSingle, i);break;
 78                                       }
 79                                   
 80                                   }//当1-9后面字符为0-9时自动机一直空转循环
 81                                       
 82                               }else{
 83                                   continue;//提前返回至for循环,判断下次输入(最后转至终态)
 84                               }
 85                               
 86                               
 87                           }else{//在小数点后面出现了非法字符
 88                                 System.out.println("ERROR:\n小数点后出现了字符"+String.valueOf(ch)); 
 89                                 Analyze.lastAnayScuccess=false;
 90                                 lastSingle=i;
 91                               continue;
 92                           }
 93                   }else{//不为小数点
 94                       continue;
 95                   }
 96                   
 97                   
 98                   
 99                }else{//如果为1-9
100                   i++;
101                   if(i<input.length()) ch=input_array[i];//取下一个字符到ch//1-9的下一个字符
102                   else{
103                       BuildUtils.getEndSingle(input, lastSingle+1, i);break;
104                       }
105                   if(ch>=‘0‘&&ch<=‘9‘){
106                       while(ch>=‘0‘&&ch<=‘9‘) {    
107                           i++;
108                           if(i<input.length()) ch=input_array[i];    
109                           else {
110                               if(lastSingle==-1)  {BuildUtils.getEndSingle(input, 0, i);    break;}
111                               else
112                                   {BuildUtils.getEndSingle(input, lastSingle, i);    break;}
113                           }
114                       }//当1-9后面字符为0-9时自动机一直空转循环
115                     
116                       
117                       
118                   }else if(ch==‘.‘){    
119                         i++;
120                         if(i<input.length()) ch=input_array[i];//取下一个字符到ch
121                           if(ch>=‘0‘&&ch<=‘9‘){//取下一个字符到ch//小数点后面的数字
122                               
123                               i++;
124                             if(i<input.length())ch=input_array[i];//取下一个字符到ch//小数点后面的后面
125                             else{ 
126                               BuildUtils.getEndSingle(input, lastSingle, i);  break;
127                             }
128                             
129                             if(ch>=‘0‘&&ch<=‘9‘){
130                                   while(ch>=‘0‘&&ch<=‘9‘) {    
131                                           i++;
132                                           if(i<input.length()) ch=input_array[i];
133                                           else{ 
134                                               BuildUtils.getEndSingle(input, lastSingle, i);    break;
135                                           }
136                                       }//当1-9后面字符为0-9时自动机一直空转循环
137                               }else{
138                                   continue;//提前返回至for循环,判断下次输入(最后转至终态)
139                               }
140                               
141                               
142                           }else{//在小数点后面出现了非法字符
143                                 System.out.println("ERROR:\n小数点后出现了字符"+String.valueOf(ch));
144                                 Analyze.lastAnayScuccess=false;
145                                 lastSingle=i;
146                                 i++;
147                               continue;
148                           }
149                       
150                   }else{
151                       continue;//提前返回至外层循环,判断此次输入(最后转至终态)
152                   }
153                       
154                   
155                   
156               }
157              
158               
159               
160               
161           }else if(ch==‘.‘){    
162                 i++;
163                 if(i<input.length()) ch=input_array[i];//取下一个字符到ch
164                   if(ch>=‘0‘&&ch<=‘9‘){//取下一个字符到ch//小数点后面的数字
165                       
166                       i++;
167                     if(i<input.length())ch=input_array[i];//取下一个字符到ch//小数点后面的后面
168                     else{ 
169                       BuildUtils.getEndSingle(input, lastSingle, i);  break;
170                     }
171                     
172                     if(ch>=‘0‘&&ch<=‘9‘){
173                           while(ch>=‘0‘&&ch<=‘9‘) {    
174                                   i++;
175                                   if(i<input.length()) ch=input_array[i];
176                                   else{ 
177                                       BuildUtils.getEndSingle(input, lastSingle, i);    break;
178                                   }
179                               }//当1-9后面字符为0-9时自动机一直空转循环
180                       }else{
181                           continue;//提前返回至for循环,判断下次输入(最后转至终态)
182                       }
183                       
184                       
185                   }else{//在小数点后面出现了非法字符
186                         System.out.println("ERROR:\n小数点后出现了字符"+String.valueOf(ch)); 
187                         Analyze.lastAnayScuccess=false;
188                         lastSingle=i;
189                         i++;
190                       continue;
191                   }
192               
193           }
194           
195           
196           
197           
198           
199           
200           
201           else{//不是数字 
202               
203               //取下的为运算符
204               if(ch==‘+‘||ch==‘-‘||ch==‘*‘||ch==‘/‘||ch==‘(‘||ch==‘)‘){
205                  if(i!=0){
206                       
207                       if(lastSingle==-1) s=input.substring(0, i);
208                       else s=input.substring(lastSingle+1, i);
209                       //将此次运算符出现的位置存储到lastSingle
210                       lastSingle=i;
211                       if(!s.isEmpty()){
212                           BuildUtils.parsertoIntOrDouble(s);
213                       }
214                    
215                       BuildUtils.parsertoSingle(ch);
216                       i++;
217                       continue;//继续判断下一字符
218                  }else{
219                       BuildUtils.parsertoSingle(ch);
220                       lastSingle=i;
221                       i++;
222                       continue;//继续判断下一字符
223                  }
224               }else{//否则出错,但需要同时记录出错字符的位置以便获取数字串
225                   
226                   //将此次非法标识符出现的位置存储到lastSingle
227                   lastSingle=i;
228                   //在任何位置出现了非法字符
229                   System.out.println("ERROR:\n出现非法标识符"+String.valueOf(ch)); 
230                   i++;
231                   continue;
232                     
233                   
234               }
235              
236               
237               
238               
239               
240           }
241           
242           
243      }
244       
245     return 0;
246       
247   }
248 
249 
250 }

 

(语法法分析类:Analyze.java)

package util;


import java.util.ArrayList;

import bean.Node;

public class Analyze {
    
    private Node particularNode=new Node(null, "#", null, null);
    private ArrayList<Node> inputStack=new ArrayList<Node>();//输入串
    private ArrayList<Node> inputQueue=new ArrayList<Node>();//输入栈
    private ArrayList<Node> singleQueue=new ArrayList<Node>();//符号栈
    private ArrayList<Integer> analyzeQueue=new ArrayList<Integer>();//分析栈(状态栈)
    private static Analyze analyze=null;
    private int statuSum=16;//该文法涉及了16个状态
    private int Action=8;//8个动作
    private int Turn=3;//3个转移
    public static boolean lastAnayScuccess=true;
    int act = 0 ;//动作  
    int turn=0;//转移
    int status=0;//初始状态
    int actionIndex=-1;
    int turnIndex=-1;
    int index;//输入串的字符下标
    int SUCCESS=0;
    int FAILE=1;
    int sindex;
    int aindex;

    Node reduceNode = null;//规约后压入符号栈的单词结点
    
    private  Analyze(){
        this.inputQueue.add(particularNode);//输入串在进行语法分析前要先将结束符压入栈底
        this.singleQueue.add(particularNode);//符号栈初始状态下为#
        this.analyzeQueue.add(0);
        //result = new StringBuilder();
    
    }
    
    public static Analyze getAnalyze(){
        if(analyze==null){
            analyze=new Analyze();
        }
        return analyze;
    }
    
    public void addNode(Node node){//初始化输入串
        inputStack.add(node);
    }
    
    public void shiftNode(Node node){//将待匹配的node移进符号栈
        singleQueue.add(node);
    }
    
    
    public void addNodeToSQ(Integer Istatus){//状态栈添加状态
        analyzeQueue.add(Istatus);
    }
    
    
    public int divceProgram(){//驱动程序
    exchange(inputStack, inputQueue);
    index=inputQueue.size()-1;
    int ti=1;//t1,t2,t3...
    if(lastAnayScuccess){//在上一步词法分析没有出错的情况下往下进行语法分析
        
        
        System.out.println("开始进行语法分析");
    
        
        while(true){   //从输入串的首单词开始判断是否移入符号栈
            
            
                    //该单词节点执行的状态跳转
                    while(turnIndex<Turn){    
                        
                        if(index>=0){
                            for(int j=0;j<Turn;j++){
                                if(inputQueue.get(index).getKey().equals(ParserType.vn[j].getSingle())){
                                    turnIndex=j;
                                    break;
                                }
                            }
                        }
                        
                        
                        
                         if(turnIndex!=-1){
                             
                             turn=ParserType.go[status][turnIndex];//true是goto表中的元素值
                             if(turn>0){
                                 status=turn;//状态跳转到goto表true所对应的值
                                 turnIndex=-1;
                                 index--;//跳转到turn步骤之后匹配下一个输入单词
                                 System.out.println("输入串剩余长度"+index);
                                 break;
                             }else{//等于0时出错
                                 ProcError();   return FAILE;
                             }
                             
                             
                         }else
                         {
                            break; 
                         }
                        
                    }
                    
                    
                        //该单词节点执行的动作
                        while(actionIndex<Action){
                            
                            
                            
                            if(index>0){
                                for(int i=1;i<Action;i++){
                                    if(inputQueue.get(index).getKey().equals(ParserType.vt[i].getSingle())){
                                        actionIndex=i;
                                        break;
                                    } 
                                    
                                }
                                if(inputQueue.get(index).getBeanTpye().equals("int")||inputQueue.get(index).getBeanTpye().equals("double")){
                                        actionIndex=0;
                                    }
                                
                            }
                            if(index==0){
                                actionIndex=7;
                            }
                    
                            
                            
                            if(actionIndex!=-1){
                                System.out.println("状态"+status);
                                System.out.println("动作下标"+actionIndex);
                                
                                    act=ParserType.action[status][actionIndex];//动作    
                                
                                 if (act == ParserType.BLANK)    {    
                                     ProcError();    System.out.println("语法错误"); return FAILE; 
                                 }else if(act==ParserType.ACC){
                                     
                                     System.out.println("该输入串符合语法要求并已被接收");
                                     System.out.println("计算结果:"+singleQueue.get(1).getValue());
                                     return SUCCESS;
                                     
                                 }else if(act>0){//进行移进操作,然后转向状态act
                                     //移进操作,将待分析的单词压入符号栈
                                     singleQueue.add(inputQueue.get(index));
                                     analyzeQueue.add(act);
                                     System.out.println(inputQueue.get(index)+"加入符号栈");
                                     System.out.println(act+"加入状态栈");
                                     System.out.println("符号栈:"+singleQueue.toString());
                                     System.out.println("状态栈:"+analyzeQueue.toString());
                                     status=act;
                                     actionIndex=-1;
                                     index--;
                                     continue;
                                     
                                 }else{//进行规约操作
                                     
                                     //此时act值小于0,取绝对值之后即为规约所用的文法产生式序号Math.abs(act);
                                     for(P p:ParserType.pset){//寻找产生式
                                         if(p.getNum()== Math.abs(act)){
                                             int noZeroNum=0;
                                             
                                             aindex=analyzeQueue.size()-1;
                                             sindex=singleQueue.size()-1;
                                             ArrayList<Node>  reduceNodeList=new ArrayList<Node>();//规约中间结果存储列表
                                            // ArrayList<Node>  saveNodeList=new ArrayList<Node>();//规约中间变量存储列表
                                             StringBuilder result=new StringBuilder();
                                             for(int i=0;i<p.getRigthExp().length;i++){
                                                 if(!p.getRigthExp()[i].toString().equals("0")){
                                                     noZeroNum++;
                                                 }
                                                 
                                             }
                                             
                                             
                                                 while(noZeroNum>0){
                                                 //存储需要规约的单词
                                                
                                                 reduceNodeList.add(singleQueue.get(sindex));
                                                
                                                 System.out.println(singleQueue.get(sindex)+"被规约");
                                                //状态栈和符号栈要移除的结点
                                                 singleQueue.remove(singleQueue.get(sindex));
                                                   if(sindex>0)    sindex--;
                                                 analyzeQueue.remove(analyzeQueue.get(aindex));//符号栈和状态的操作需同步
                                                 if (aindex>0)    aindex--;
                                                 noZeroNum--;
                                             }
                                                 
                                        
                                 V ch=p.getLeftV();//获取规约后的单词,
                                 int leftVindex=0;
                                 //找到在goto表对应的turnIndex值
                                 for(V v:ParserType.vn){
                                     if(!v.equals(ch)){
                                         leftVindex++;
                                     }else
                                         break;
                                 }
                                    
                                             
                                        
                                             for(String str:p.getRigthExp()){
                                                result.append(str);
                                             }
                                             String rigthExp=result.toString();
                                             System.out.println("rigthExp:"+rigthExp);
                                        
                                             if(rigthExp.contains("+")||rigthExp.contains("-")||rigthExp.contains("*")||rigthExp.contains("/")){
                                                     //规约后的单词四元式
                                                     Node saveNode=new Node(p.getRigthExp()[1].toString(),reduceNodeList.get(2).getValue().toString(),
                                                             reduceNodeList.get(0).getValue().toString(),"t"+(ti++));
                                                    // saveNodeList.add(saveNode);
                                                    //输出中间四元式
                                                     System.out.println(saveNode.toString());
                                                 
                                                
                                                 //将单词串转换成真实的字符运算并用reduceNode存储中间结果
                                                 switch(p.getRigthExp()[1].toString()){
                                                 case "+":
                                                     reduceNode=ReduceTools.reduceByAdd(reduceNodeList, p);break;
                                                                                                      
                                                 case "-":
                                                     reduceNode=ReduceTools.reduceByJian(reduceNodeList, p); break;
                                      
                                                 case "*":
                                                     reduceNode=ReduceTools.reduceByCheng(reduceNodeList, p);break;
                                                                     
                                                 case "/": 
                                                     reduceNode=ReduceTools.reduceByChu(reduceNodeList, p); break;
                                                    
                                                 default:
                                                         break;
                                                
                                                     
                                                 }

                                             }else if(rigthExp.contains("i")){
                                                 
                                                 reduceNode=ReduceTools.reduceFromi(reduceNodeList, p);
                                                 
                                             }else if(rigthExp.contains("(")&&rigthExp.contains(")")){
                                                 
                                                 reduceNode=ReduceTools.reduceByKuoHao(reduceNodeList, p);
                                                 
                                             }/*else if(rigthExp.contains("-F")){//F->-F
                                                 reduceNode=ReduceTools.reduceByFu(reduceNodeList, p);
                                                 
                                             }*/else{//T->F//E->T//S->E
                                                 reduceNode=ReduceTools.reduceFromOther(reduceNodeList, p);
                                             }
                                    
                                             
                                             
                                            
                                             
                                             singleQueue.add(reduceNode);//规约之后将中间结果压入符号栈
                                             sindex++;
                                             status=ParserType.go[analyzeQueue.get(aindex)][leftVindex];
                                             analyzeQueue.add(status);//向状态栈添加规约后的状态
                                             aindex++;
                                             System.out.println(singleQueue.get(sindex)+"加入符号栈");    
                                             System.out.println(analyzeQueue.get(aindex)+"加入状态栈");
                                             System.out.println("符号栈:"+singleQueue.toString());
                                             System.out.println("状态栈:"+analyzeQueue.toString());
                                             actionIndex=-1;
                                             break;
                                         }
                                     } 
                                     //规约阶段涉及goto操作
                                 }
                    }else{
                            break;    
                    }
                            
                            
                            
                    
                    
                        }
                        
                
                }
        
    
        
    }else{
        WorldError();
    }
    return 0;
          
        
        
        
    }

    private void ProcError() {
        // TODO Auto-generated method stub
        System.out.println("语法错误");
        
    }
    
    private void WorldError() {
        // TODO Auto-generated method stub
        System.out.println("存在词法错误,无法进行语法分析");
        
    }
    //栈数据倒灌
    public void exchange(ArrayList<Node> list1,ArrayList<Node> list2){
        for(int i=list1.size()-1;i>=0;i--){
            list2.add(list1.get(i));
        }
    }
    
}

 

  具体源码见我的GitHub https://github.com/kingxiusam/PLTest

(注意:由于能力有限,源码有一些bug,希望大家可以帮忙修改完善,如果觉得不错可以给个星)

表达式计算器的设计与实现