现在的位置: 首页 > 综合 > 正文

算符优先计算器

2013年07月25日 ⁄ 综合 ⁄ 共 11399字 ⁄ 字号 小 中 大 ⁄ 评论关闭
Code:
  1. import java.util.*;   
  2. import java.io.*;   
  3.   
  4. //Evaluator class interface: evaluate infix expressions   
  5. //construction:with a string   
  6. //************public operations***************   
  7. //long getValue() -->return value of infix expression   
  8. //*********************************************   
  9. //   
  10. public class Evaluator {   
  11.   
  12.     /**made by Mark Allen Weiss   
  13.      *  revise @blacksapper  
  14.      */   
  15.        
  16.        //不是显式输出表达式.而是把他们送到后缀机   
  17.         private static final int EOL=0;   
  18.         private static final int VALUE=1;   
  19.         private static final int OPAREN=2;   
  20.         private static final int CPAREN=3;   
  21.         private static final int EXP=4;   
  22.         private static final int MULT=5;   
  23.         private static final int DIV=6;   
  24.         private static final int PLUS=7;   
  25.         private static final int MINUS=8;   
  26.         private static final int MOD=9;   
  27.         private static final int C=10;//排列   
  28.         private static final int P=11;//组合   
  29.         private static final int GCD=12;//欧几里得运算.最大公约数   
  30.         //part  A   
  31.         private static class Precedence   
  32.         {/*程序7-16*/  
  33.             public int inputSymbol;   
  34.             public int topOfStack;   
  35.             public Precedence(int inSymbol ,int topSymbol)   
  36.             {   
  37.                 inputSymbol=inSymbol;   
  38.                 topOfStack=topSymbol;   
  39.             }   
  40.         }   
  41.         //preTable matches order of token enumeration   
  42.         //用于计算中缀表达式的优先级表   
  43.         //用于计算栈顶哪些符号应该弹出   
  44.         //左结合的运算符在栈中级别比外面高1右接合的比外面的小1.   
  45.         private static Precedence[] precTable=   
  46.         {   
  47.             new Precedence(0  , -1),//EOL   
  48.             new Precedence(0  ,  0),//VALUE   
  49.             new Precedence(100,  0),//OPAREN   
  50.             new Precedence(0  , 99),//CPAREN   
  51.             new Precedence(10 ,  9),//EXP   
  52.             new Precedence(5  ,  6),//MULT   
  53.             new Precedence(5  ,  6),//DIV   
  54.             new Precedence(1  ,  2),//PLUS   
  55.             new Precedence(1  ,  2), //MINUS   
  56.             new Precedence(5  ,  6),//MOD   
  57.             new Precedence(11 , 12),//排列   
  58.             new Precedence(11 , 12),//组合   
  59.             new Precedence(7  ,  8)//GCD要重新改写优先级了.欧几里得运算   
  60.             //part B   
  61.         };//可能有错   
  62.            
  63.            
  64.     private static class Token   
  65.     {/*程序7-11*/  
  66.         public Token()   
  67.         {   
  68.             this (EOL);   
  69.         }   
  70.         public Token(int t)   
  71.         {   
  72.             this(t,0);   
  73.         }   
  74.         public Token(int t,long v)   
  75.         {   
  76.             type=t;   
  77.             value=v;   
  78.         }   
  79.            
  80.         public int getType()   
  81.         {   
  82.             return type;   
  83.         }   
  84.         public long getValue()   
  85.         {   
  86.             return value;   
  87.         }   
  88.         private int type=EOL;   
  89.         private long value=0;   
  90.     }   
  91.        
  92.        
  93.     private static class EvalTokenizer   
  94.     {/*程序7-11*/  
  95.         public EvalTokenizer(StringTokenizer is)   
  96.         {str=is;}   
  97.         /**得到标记序列,并知道它读入的值是什么  
  98.          * find the next token,skipping blacks,and return it.  
  99.          * for value token,place the process value in currentValue  
  100.          * print error message if input is unrecognized  
  101.          * 输入的没定义则抛出异常为没定义.  
  102.          */  
  103.         public Token getToken()   
  104.         {/*程序清单7-12*/  
  105.             long theValue;   
  106.             if(!str.hasMoreTokens())   
  107.                 return new Token();   
  108.             //PART C   
  109.             String s = str.nextToken();   
  110.             if(s.equals(""))return getToken();   
  111.             if(s.equals("^"))return new Token(EXP);   
  112.             if(s.equals("/"))return new Token(DIV);   
  113.             if(s.equals("*"))return new Token(MULT);   
  114.             if(s.equals("("))return new Token(OPAREN);   
  115.             if(s.equals(")"))return new Token(CPAREN);   
  116.             if(s.equals("+"))return new Token(PLUS);   
  117.             if(s.equals("-"))return new Token(MINUS);   
  118.             if(s.equals("%"))return new Token(MOD);   
  119.             if(s.equals("P"))return new Token(P);   
  120.             if(s.equals("C"))return new Token(C);   
  121.             if(s.equals("G"))return new Token(GCD);   
  122.             try  
  123.             {theValue=Long.parseLong(s);}   
  124.             catch(NumberFormatException e)   
  125.             {   
  126.                 System.err.println("Parse error");   
  127.                 return new Token();   
  128.             }   
  129.             return new Token(VALUE,theValue);   
  130.                
  131.            
  132.         }   
  133.            
  134.         private StringTokenizer str;   
  135.     }   
  136.        
  137.        
  138.     public  Evaluator (String s)   
  139.     {   
  140.         opStack=new Stack<Integer>();opStack.push(EOL);   
  141.            
  142.         postfixStack=new Stack<Long>();   
  143.         str=new StringTokenizer(s,"+*-/^()%PCG",true);   
  144.         //PART D    }   
  145.        
  146.        
  147.     public long getValue()   
  148.     {/*程序清单7-13*/  
  149.         /**  
  150.          * 重复读取一个标记并处理之.  
  151.          */  
  152.         EvalTokenizer tok=new EvalTokenizer(str);   
  153.             Token lastToken;   
  154.             do{   
  155.             lastToken=tok.getToken();   
  156.             processToken(lastToken);   
  157.             }while(lastToken.getType()!=EOL);   
  158.                
  159.             if(postfixStack.isEmpty())   
  160.             {   
  161.                 System.err.println("Missing operand!");   
  162.                 return 0;   
  163.             }   
  164.             long theResult=postfixStack.pop();   
  165.             if(!postfixStack.isEmpty())   
  166.             {System.err.println("Warning:missing operators!");}   
  167.             return theResult;   
  168.            
  169.     }   
  170.        
  171.        
  172.     private Stack<Integer> opStack;  //Operator stack for conversion   
  173.     private Stack<Long> postfixStack;  //Stack for postfix machine   
  174.     private StringTokenizer str;   //StringTokenizer stream   
  175.     /**  
  176.      * after a token is read,use operator precedence parsing   
  177.      * are detected here  
  178.      * 用来遍历输入行  
  179.      */  
  180.        
  181.     private void processToken(Token lastToken)   
  182.     {/*程序清单7-17*/  
  183.         /**  
  184.          * 遇到运算符就放到后缀栈中.如果遇到右括号就重复计算栈中的项直到遇到左括号为止  
  185.          * 否则就是处理一般运算符  
  186.          */  
  187.         int topOp;   
  188.         int lastType=lastToken.getType();   
  189.         switch(lastType)   
  190.         {   
  191.         case VALUE:   
  192.             postfixStack.push(lastToken.getValue());   
  193.             return;   
  194.         case CPAREN:   
  195.             while((topOp=opStack.peek())!=OPAREN&&topOp!=EOL)   
  196.                 binaryOp(topOp);   
  197.             if(topOp==OPAREN)   
  198.                 opStack.pop();//get rid of opening parentheseis   
  199.             break;   
  200.             default:           
  201.                    
  202.                 while(precTable[lastType].inputSymbol<=   
  203.                     precTable[topOp=opStack.peek()].topOfStack)   
  204.                     binaryOp(topOp);   
  205.                     if(lastType!=EOL)   
  206.                         opStack.push(lastType);   
  207.             break;   
  208.         }   
  209.     }   
  210.        
  211.        
  212.     private long postfixpop()    //getTop()   
  213.     {/*程序清单7-14*/  
  214.         /**  
  215.          * 后缀机栈的弹出.必要时候抛出异常.  
  216.          */  
  217.         if(postfixStack.isEmpty())   
  218.         {   
  219.             System.err.println("Missing operand");   
  220.             return 0;   
  221.         }   
  222.         return postfixStack.pop();   
  223.     }   
  224.        
  225.     //重写的方法    
  226. PART E   
  227.      private static long pow( long x, long n )   
  228.         {   
  229.          /**  
  230.           * pow in long   
  231.           */  
  232.             if( x == 0 )   
  233.             {   
  234.                 if( n == 0 )   
  235.                     System.err.println( "0^0 is undefined" );   
  236.                 return 0;   
  237.             }   
  238.             if( n < 0 )   
  239.             {   
  240.                 System.err.println( "Negative exponent" );   
  241.                 return 0;   
  242.             }   
  243.             if( n == 0 )   
  244.                 return 1;   
  245.             if( n % 2 == 0 )   
  246.                 return pow( x * x, n / 2  );   
  247.             else  
  248.                 return x * pow( x, n - 1 );   
  249.         }   
  250.         private static long pailie(long lhs, long rhs) {   
  251.             long lhs1;   
  252.             if(lhs==rhs)   
  253.                 return 1;   
  254.             else  
  255.             {   
  256.             lhs1=lhs-1;    
  257.             }   
  258.             return lhs*pailie(lhs1,rhs);   
  259.         }   
  260.         private static long zuhe(long lhs, long rhs) {   
  261.             long output=0;   
  262.             output=pailie(lhs,rhs)/jiecheng(lhs);   
  263.             return output;   
  264.         }   
  265.         
  266.         
  267.     private static long jiecheng(long n) {   
  268.         if(n==0 || n==1)   
  269.         {   
  270.             return 1;   
  271.         }   
  272.         return jiecheng(n-1)*n;   
  273.         }   
  274.     private static long gcd(long n,long m){   
  275.   
  276.   
  277.               if(m == 0)   
  278.   
  279.                return n;   
  280.   
  281.               else  
  282.   
  283.                return gcd(m,n%m);   
  284.   
  285.     }   
  286.     //end重写的方法结束   
  287.   
  288.   
  289.     private void binaryOp(int topOp)   
  290.     {/*程序清单7-15*/  
  291.         /**  
  292.          * 运算符栈的栈顶用作后缀机栈的最上面两项.然后用得出结果替换掉它们.也将运算符栈顶弹出  
  293.          */  //part F
  294.         if(topOp==OPAREN)   
  295.         {   
  296.             System.err.println("Unbalanced parentheses");   
  297.             opStack.pop();   
  298.             return;   
  299.         }   
  300.         long rhs=postfixpop();   
  301.         long lhs=postfixpop();   
  302.            
  303.         if(topOp==EXP)   
  304.             postfixStack.push(pow(lhs,rhs));   
  305.         else if(topOp==MOD)   
  306.             postfixStack.push(lhs%rhs);   
  307.         else if(topOp==P)   
  308.         {   
  309.             if(rhs<lhs)   
  310.             {   
  311.                 postfixStack.push(pailie(lhs,rhs));   
  312.             }   
  313.             else  
  314.             {   
  315.             System.err.println("input error");   
  316.             postfixStack.push(lhs);   
  317.             }   
  318.         }   
  319.         else if(topOp==GCD)   
  320.         {   
  321.             if(rhs<lhs)   
  322.             {   
  323.                 postfixStack.push(gcd(lhs,rhs));   
  324.             }   
  325.             else  
  326.                 postfixStack.push(gcd(rhs,lhs));   
  327.         }   
  328.         else if(topOp==C)   
  329.         {   
  330.             if(rhs<lhs)   
  331.             {   
  332.                 postfixStack.push(zuhe(lhs,rhs));   
  333.             }   
  334.             else  
  335.             {   
  336.             System.err.println("input error");   
  337.             postfixStack.push(lhs);   
  338.             }   
  339.         }   
  340.         else if(topOp==PLUS)   
  341.             postfixStack.push(lhs+rhs);   
  342.         else if(topOp==MINUS)   
  343.             postfixStack.push(lhs-rhs);   
  344.         else if(topOp==MULT)   
  345.             postfixStack.push(lhs*rhs);   
  346.         else if(topOp==DIV)   
  347.             if(rhs!=0)   
  348.                 postfixStack.push(lhs/rhs);   
  349.             else  
  350.             {   
  351.                 System.err.println("Division by zero");   
  352.                 postfixStack.push(lhs);   
  353.             }   
  354.         opStack.pop();   
  355.            
  356.     }   
  357.        
  358.        
  359.   
  360.   
  361.   
  362.   
  363.   
  364.   
  365.     public static void main(String[] args) {   
  366.         String str;   
  367.         BufferedReader in=new BufferedReader(new InputStreamReader(System.in));   
  368.         try{   
  369.             System.out.println("Enter expressions,1 per line");   
  370.             while((str=in.readLine())!=null)   
  371.             {   
  372.                 System.out.println("Read:"+str);   
  373.                 Evaluator ev=new Evaluator(str);   
  374.                 System.out.println(ev.getValue( ));   
  375.                 System.out.println("Enter next expression");   
  376.             }   
  377.         }   
  378.         catch(IOException e)   
  379.         {e.printStackTrace();}   
  380.   
  381.     }   
  382.        
  383.   
  384. }   

Mark Allen Weiss教授写的算符优先计算器.我拿来山寨了一下.增加了四个运算.%模运算  C排列运算 P组合运算 G求最大公约数运算.

如果想像我一样加入方法.在part ABCDE五个地方加入.

A表示方法. B表示优先级.分别是栈外优先级和栈内优先级.

为什么^的后面的优先级比前面高而其他的一律低.左括号的又不一样呢.运算^的是从右往左运算的而不是从左往右.这个是数学计算的规定.好比 2^2^5=2^32  而不是 4^5  左括号在栈外优先级是很高的.在栈内 (+)当然是先算+了.所以栈内的优先级不最低.

C表示识别的字符的长相分别对应的给定的那个定义的算符.

D规定了运算符长相为合法长相.这个是我破解这个的难点.看出来了也就容易了.我怕规定GCD会引起二义性.就用G运算代替.

E就是重写的方法.以后要写自己加.

F就是规定进栈的运算.教授重写了POW运算.我要算的除了%都重写了方法.

昨天问老师这个怎么弄.怎么加.他说东西都写好了.你为什么还要重写方法?我说Java课设不止是Java课设.以后可能用汇编重写方法.这个是终极目的.

说明书.运算可以再long范围内运算加减乘除乘方排列组合和最大公约数运算.

求最小公倍数运算

7*8/7G8 或者 7*8/8G7

求阶乘运算

nP1

算符优先级

+  =  -  <  *  =  /  =  %  <  G < P = C <(  )

P C 的输入只能左边比右边大  ^乘方运算是从右往左其他一概从左往右运算.

这个系统不支持单目运算符和小数运算.如果想用到开方运算就要重写方法用泰勒公式或者麦克劳林公式展开了.

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞