2014年5月15日星期四

A wonderful interview subject encountered great God who seek answers ! ! !

Topic roughly String eveal (String s) This method is meant to return a result of the input parameter is a string of expression If ( 1 +1 ) * 3 / 2 +1 this string of the form you want to return a result
------ Solution ------- -------------------------------------
this is a core function of formula calculator
Here is a function of my software fully meets your requirements , but is VB6 code.

Option Explicit
Dim Hds As String
Private Sub Form_Load ()
MsgBox "(1 +1) × 3 ÷ 2 +1 =" & GetJSResult ("(1 +1) × 3 ÷ 2 +1")
End Sub
Public Function GetJSResult (ByVal Jsgs As String) As Currency ' recursive mathematical formula to calculate the
Dim Kh1 As Long, Kh2 As Long, halfKh As Long
Dim i As Long, jsgs1 As String
jsgs1 = Jsgs
' to find out first on the outermost brackets and its contents as a parameter of the function call GetJSResult, continue stripping brackets
Kh1 = InStr (1, jsgs1, "(")
If Kh1> 0 Then
halfKh = halfKh + 1
For i = Kh1 + 1 To Len (jsgs1)
If Mid (jsgs1, i, 1) = "( "Then halfKh = halfKh + 1
If Mid (jsgs1, i, 1) = ") "Then
halfKh = halfKh - 1
If halfKh = 0 Then '
Kh2 = i
jsgs1 = Left (jsgs1, Kh1 - 1) & GetJSResult (Mid (jsgs1, Kh1 + 1, Kh2 - Kh1 - 1)) & Right (jsgs1, Len (jsgs1) - Kh2)
Hds = Hds ; & vbCrLf & "=" & jsgs1
Kh1 = InStr (1, jsgs1, "(")
If Kh1 = ; 0 Then
Exit For
Else
i = Kh1 - 1
End If
End If
End If
Next
End If
' telephone number so far been completely stripped , based on the way after the first addition and subtraction , multiplication and division calculations, and returns the results
' calculate multiplication and division fh = "+ - × ÷"
Dim Fh1 As Long, Fh2 As Long, Fh3 As Long, Num1 As String, Num2 As String, j As Long, lsbl As String
jsgs1 = Replace (jsgs1, ".", ".")
For i = 1 To Len (jsgs1)
'--- find the first multiplication and division number
Fh1 = 0: Fh2 = 0
Fh1 = InStr (1, jsgs1, "×")
Fh2 = InStr (1, jsgs1, "÷")
If (Fh1 0) Or Fh2 = 0 Then
Fh2 = Fh1
End If

If Fh2 = 0 Then Exit For ' where no multiplication and division , out of the loop execution down

'----- looking for multiplication and division number in front of the figure
For j = Fh2 - 1 To 1 Step -1
lsbl = Mid (jsgs1, j, 1)
If lsbl = "+" Or lsbl = " - "Then
Num1 = Val (Mid (jsgs1, j ; + 1, Fh2 - j - 1))
Fh1 = j
Exit For
End If
Next
If j = 0 Then
Num1 = Val (Left (jsgs1, Fh2 - 1))
Fh1 = j
End If

'----- look behind the figures , multiplication and division number
For j = Fh2 + 1 To Len (jsgs1)
lsbl = Mid (jsgs1, j, 1)
If lsbl = "+" Or lsbl = " - "Or lsbl =" × "Or lsbl =" ÷ "Then
Num2 = Val (Mid (jsgs1, Fh2 ; + 1, j - Fh2 - 1))
Fh3 = j
Exit For
End If
Next
If j> Len (jsgs1) Then
Num2 = Val (Right (jsgs1, Len (jsgs1) - Fh2))
Fh3 = j
End If
'----- for computing
lsbl = Num1 & Mid (jsgs1, Fh2, 1) & Num2
If Mid (jsgs1, Fh2, 1) = "×" Then
Num1 = Val (Num1) * Val (Num2)
Else
Num1 = Val (Num1) / Val (Num2)
End If
'--------
jsgs1 = Left (jsgs1, Fh1) & Num1 & Right (jsgs1, ; Len (jsgs1) - Fh3 + 1)
Hds = Hds & vbCrLf & "=" & jsgs1
i = 1
Next
' calculation of addition and subtraction
Dim Jjjg As Currency
If InStr (1, jsgs1, "+")> 0 Or InStr (1, jsgs1, " ; - ")> 0 Then
Num1 = "": Num2 = "": Fh1 = 0 : Jjjg = 0
For i = 1 To Len (jsgs1)
lsbl = Mid (jsgs1, i, 1)
If lsbl = "+" Or lsbl = " - "Then
If Fh1 = 0 Then
Fh1 = i
Else
lsbl = Mid (jsgs1, Fh1, 1)
If lsbl = ; "+" Then
Jjjg = Val (Num1) + Val (Num2)
Else
Jjjg = Val (Num1) - Val (Num2)
End If
Num1 = Jjjg : Num2 = "": Fh1 = i
End If
Else
If Fh1 = 0 Then
Num1 = Num1 ; & lsbl
Else
Num2 = Num2 ; & lsbl
End If
End If
Next
If i> Len (jsgs1) Then
lsbl = Mid (jsgs1, Fh1, 1)
If lsbl = "+" Then
Jjjg = Val (Num1) + Val (Num2)
Else
Jjjg = Val (Num1) - Val (Num2)
End If
End If
jsgs1 = Jjjg
End If
'------------------
GetJSResult = Val (jsgs1)
End Function

------ Solution ------------------------------------ --------
do not want to call upstairs java js method can also be used to resolve a pure java
idea is , according to the first bracket , then multiplication and division , addition and subtraction of the last ideas, instead of using a value expression ,
(1 +1) * 3/2 +1
2 * 3/2 +1
6/2 +1
3 +1
4
code below
public class Test1 {

private String parentheses = "\\((\\d+((\\+|\\-|\\*|\\/))?)+\\)"; //匹配括号内的
private String multiplyDivide = "\\d+(\\*|\\/)\\d+";//匹配乘除的
private String addSubtract = "\\d+(\\+|\\-)\\d+";//匹配加减的

//括号
private String resultParentheses(String s) {
Pattern p = Pattern.compile(parentheses);
Matcher m = p.matcher(s);
String ss = s;
while (m.find()) {
String sTemp = m.group();
String multiplyDivide = resultMultiplyDivide(sTemp);
String addSubtract = resultAddSubtract(multiplyDivide);
addSubtract = addSubtract.substring(1,addSubtract.length()-1);//算出结果后去掉括后
ss = ss.replace(sTemp, addSubtract);//把括号算出的值替换原来的表达式
m = p.matcher(ss);//递归(重新匹配)
}
return ss;
}

//乘除
private String resultMultiplyDivide(String s) {
Pattern p = Pattern.compile(multiplyDivide);
Matcher m = p.matcher(s);
int result = 0;
String ss = s;
while (m.find()) {
String sTemp = m.group();
int fristNum = 0;
int secondNum = 0;
int sp = 0;
if (sTemp.contains("*")) {
sp = sTemp.indexOf("*");
fristNum = Integer.valueOf(m.group().substring(0, sp));
secondNum = Integer.valueOf(sTemp.substring(sp + 1,sTemp.length()));
result = fristNum * secondNum;
} else if (sTemp.contains("/")) {
sp = sTemp.indexOf("/");
fristNum = Integer.valueOf(m.group().substring(0, sp));
secondNum = Integer.valueOf(sTemp.substring(sp + 1,sTemp.length()));
result = fristNum / secondNum;
}
ss = ss.replace(sTemp, String.valueOf(result));//用算出的值替换原来的表达式
m = p.matcher(ss);//递归(重新匹配)
}
return ss;
}

//加减
private String resultAddSubtract(String s) {
Pattern p = Pattern.compile(addSubtract);
Matcher m = p.matcher(s);
int result = 0;
String ss = s;
while (m.find()) {
String sTemp = m.group();
int fristNum = 0;
int secondNum = 0;
int sp = 0;
if (sTemp.contains("+")) {
sp = sTemp.indexOf("+");
fristNum = Integer.valueOf(m.group().substring(0, sp));
secondNum = Integer.valueOf(sTemp.substring(sp + 1,sTemp.length()));
result = fristNum + secondNum;
} else if (sTemp.contains("-")) {
sp = sTemp.indexOf("-");
fristNum = Integer.valueOf(m.group().substring(0, sp));
secondNum = Integer.valueOf(sTemp.substring(sp + 1,sTemp.length()));
result = fristNum - secondNum;
}
ss = ss.replace(sTemp, String.valueOf(result));//用算出的值替换原来的表达式
m = p.matcher(ss);//递归(重新匹配)
}
return ss;
}

public static void main(String[] args) {
Test1 t = new Test1();
String s = "(2*1+5*5/10+1)+(1+2)*100";
String a = t.resultParentheses(s);//先算括号的
String b = t.resultMultiplyDivide(a);//再算乘除
String c = t.resultAddSubtract(b);//最后加减
System.out.println(c);
}

just wrote a rough idea of ​​the realization , that you can, and then optimize their own .
------ For reference only ----------------- ----------------------
first string in the value forced into int type , do the deal
------ For reference only ---------------------------------------
; you mean to use regular expressions ? Otherwise, the inside of the operator not to judge
------ For reference only ------------------- --------------------
you mean to use regular expressions ? Otherwise, the inside of the operator not to judge  
you can do:
int a = Integer.parseInt (str.charAt ( 1 ) + "" ) ;
int b = Integer.parseInt (str.charAt (3) + "");
int c = Integer.parseInt (str.charAt (6) + "");
int d = Integer.parseInt (str.charAt (8) + "");
int e = Integer.parseInt (str.charAt ( 10 ) + "" ) ;
int sum = (a + b) * c / d + e

------ For reference only ---------------------------------- -----
this is compiler theory test you ..
------ For reference only ---------------------- -----------------
you mean to use regular expressions ? Otherwise, the inside of the operator not to judge          
you can do:   
int a = Integer.parseInt (str.charAt ( 1 ) + "" ) ;   
int b = Integer.parseInt (str.charAt (3) + "");   
int c = Integer.parseInt (str.charAt (6) + "");   
int d = Integer.parseInt (str.charAt (8) + "");   
int e = Integer.parseInt (str.charAt ( 10 ) + "" ) ;   
int sum = (a + b) * c / d + e   
  string if it is not fixed , then you have to deal with them every position to make a judgment , a little bit of trouble
------ For reference only ---------- -----------------------------
you mean by regular expressions ? Otherwise, the inside of the operator not to judge                
you can do:     
int a = Integer.parseInt (str.charAt ( 1 ) + "" ) ;     
int b = Integer.parseInt (str.charAt (3) + "");     
int c = Integer.parseInt (str.charAt (6) + "");     
int d = Integer.parseInt (str.charAt (8) + "");     
int e = Integer.parseInt (str.charAt ( 10 ) + "" ) ;     
int sum = (a + b) * c / d + e     
       string if it is not fixed , then you have to deal with them every position to make a judgment , a little bit of trouble   not fixed. . . And I used to be handwritten . . The above clearly shows a machine test alas. . .
------ For reference only ---------------------------------- -----
not. . . is a test machine but the front desk said that the pen hard questions no way I did not write it. . That paper has been written questions that are machine
------ For reference only ---------------------- -----------------
remember a java processing js eval method is not called this method ?
------ For reference only -------------------------------------- -
String do(String str){
if (str含有2个以上符号){
找到最低级别的符号分割成2段;
do (前段) "根据符号连接动作" do(后段);
}else{
简单的一元算术
}

general idea is this , no written code does not know can not be written ;
Another from two stacks , with a similar form of 2-tree traversal do
------ For reference only ---------------- -----------------------
which is the subject of the request js written in java
- ---- For reference only ---------------------------------------
me try to see the following information
------ For reference only -------------------------------- -------
which is the subject of the request js written in java  
This is the java , and this is the java program , the results obtained js .
------ For reference only -------------------------------------- -
this requirement is subject js written in java  
public static void jsTest(){
ScriptEngineManager mgr = new ScriptEngineManager(); 
ScriptEngine engine = mgr.getEngineByName("JavaScript");
try{
String script = "function js(){return (1+1)*3/2+1; }";
engine.eval(script);
Invocable inv = (Invocable) engine;   
Double res=(Double)inv.invokeFunction("js");   
System.out.println(res);    
}catch(Exception e){
e.printStackTrace();
}

}

I do not know this may not be for reference only.
------ For reference only -------------------------------------- -
this requirement is subject js written in java          
  
public static void jsTest(){
ScriptEngineManager mgr = new ScriptEngineManager(); 
ScriptEngine engine = mgr.getEngineByName("JavaScript");
try{
String script = "function js(){return (1+1)*3/2+1; }";
engine.eval(script);
Invocable inv = (Invocable) engine;   
Double res=(Double)inv.invokeFunction("js");   
System.out.println(res);    
}catch(Exception e){
e.printStackTrace();
}

}
  
I do not know this may not be for reference only.   can be the outcome , but why write js code ? Find principle
------ For reference only -------------------------------- -------
learn .......
------ For reference only ------------------- --------------------
to a wonderful way .
Create a new Java Class with the passed in String, and then compile and run the Java class , come to the operation result ( you can write to the file ) , and even dynamically create objects with interface way to call a method of calculation .
such as shell scripts can also generate , python scripts , run to the result .
------ For reference only -------------------------------------- -

directly jruby it.
------ For reference only -------------------------------------- -
this requirement is subject js written in java                
    
public static void jsTest(){
ScriptEngineManager mgr = new ScriptEngineManager(); 
ScriptEngine engine = mgr.getEngineByName("JavaScript");
try{
String script = "function js(){return (1+1)*3/2+1; }";
engine.eval(script);
Invocable inv = (Invocable) engine;   
Double res=(Double)inv.invokeFunction("js");   
System.out.println(res);    
}catch(Exception e){
e.printStackTrace();
}

}
    
I do not know this may not be for reference only.        can be the outcome , but why write js code ? Find principle  
This is the java ' js analytical methods , specific principles tell, on the Internet and look it.
------ For reference only -------------------------------------- -
data structure when the school had used to evaluate the expression stack value.
but a little pit father handwritten
------ For reference only ----------------------------- ----------
1 want a good answer on the use of the stack .
2 want to go back to fight nausea SQL, JDBC calls derby database to perform a direct result.
------ For reference only -------------------------------------- -
not use the stack, expressed concern
------ For reference only -------------------------------------- -
not that what the calculator function
------ For reference only --------------------------- ------------
 test DFA ah
------ For reference only ------------------------------- --------
how I feel this is a test push and pop ? Looks like data structure inside this part , can not remember ......
------ For reference only ----------------------- ----------------
had not learned java
------ For reference only --------------- ------------------------
Haha , I also think of using the stack , estimates do it .
------ For reference only -------------------------------------- -
this should be achieved using a recursive function , the interception of incoming characters , read the function returns the result of the current node is returned ( to enter the next cycle , the remaining portion of the incoming , read ) , recursive functions incoming characters in turn traversal, if it is digital it down to read, I read not digital content will be read into the strong int, read character is the operator , and then read the right operand , read ) return result , read the comparison operator precedence then read operands ; finally returns are calculated in accordance with the priority of the final result ;
------ For reference only --------- ------------------------------
this difficult ah. It is a test of compiler theory .
equivalent to writing a compiler
------ For reference only ---------------------------- -----------

previously seen a resolve this calculation , the principle is the first in which the contents are read out, after doing calculations
------ For reference only according to the priority ------- --------------------------------
how to compare the priority ?
------ For reference only -------------------------------------- -
suffix expressions have the impression that mess with stacks of
------ For reference only ---------------------- -----------------
this code is N years ago , did not improve optimization
------ For reference only ---------------------------------------
learn .... < br> ------ For reference only ---------------------------------------
this is a classic problem of operator precedence , how wonderful would be a problem ?
with two stacks , one stack kept a stack stored value operator, depending on the priority stack stack operation , the amount on line 40 of the code looks like .
regular upstairs are used, it is not funny ?
------ For reference only ---------------------- -----------------
remember is " infix turn suffix" problem !
------ For reference only -------------------------------------- -
see various replies to feel good about the data structure of catching
------ For reference only -------------------- -------------------


In fact, there are better methods of nausea , direct write MAIN culvert directly the result , more disgusting he
------ For reference only ---------- -----------------------------
first string in the value forced into int type , do the deal
------ For reference only -------------------------------------- -
lazy dynamic compilation java built-in method calls and call dynamic languages ​​with 13 F -box approach method , otherwise by parsing strings , according to the priority of doing arithmetic symbols into recursive layers until the symbol for the lowest level computing breaks up
------ For reference only ------------------------------------ ---

learned
------ For reference only ------------------------ ---------------
seemed compiler theory test . first into postfix expression , in calculating
------ For reference only --------------------------- ------------
learn
------ For reference only ---------------------------------------
 how do I feel a bit simple , not regular use ASCII, so few characters , one by one judge to know ,
------ For reference only ---------------------------- -----------
1, using the stack to count ;
2, compiler theory lexical analysis of the DFA , LL (1) grammar analysis , and then traverse the child nodes , recursively calculated results .
------ For reference only -------------------------------------- -
upstairs regex wrote a very good
------ For reference only ------------------------ ---------------
20 minutes gave me.

import java.math.BigDecimal;
import java.util.regex.Matcher;
import java.util.regex.Pattern;


public class Eveal {
    public static void main(String[] args) {
        System.out.println(eveal("(1+1)*3/2+1"));
    }

    public static String eveal(String s) {
        return String.valueOf(arithmetic(s));
    }

    //[REF_START][http://www.2cto.com/kf/201207/142436.html]
    public static double arithmetic(String exp){
        String result = parseExp(exp).replaceAll("[\\[\\]]", "");
        return Double.parseDouble(result);
    }

    private static String parseExp(String expression){
        expression=expression.replaceAll("\\s+", "").replaceAll("^\\((.+)\\)$", "$1");
        String minExp="^((\\d+(\\.\\d+)?)|(\\[\\-\\d+(\\.\\d+)?\\]))[\\+\\-\\*\\/]((\\d+(\\.\\d+)?)|(\\[\\-\\d+(\\.\\d+)?\\]))$";

        if(expression.matches(minExp)){
            String result=calculate(expression);
            return Double.parseDouble(result)>=0?result:"["+result+"]";
        }

        String noParentheses="^[^\\(\\)]+$";
        String priorOperatorExp="(((\\d+(\\.\\d+)?)|(\\[\\-\\d+(\\.\\d+)?\\]))[\\*\\/]((\\d+(\\.\\d+)?)|(\\[\\-\\d+(\\.\\d+)?\\])))";
        String operatorExp="(((\\d+(\\.\\d+)?)|(\\[\\-\\d+(\\.\\d+)?\\]))[\\+\\-]((\\d+(\\.\\d+)?)|(\\[\\-\\d+(\\.\\d+)?\\])))";

        if(expression.matches(noParentheses)){
            Pattern patt=Pattern.compile(priorOperatorExp);
            Matcher mat=patt.matcher(expression);
            if(mat.find()){
                String tempMinExp=mat.group();
                expression=expression.replaceFirst(priorOperatorExp, parseExp(tempMinExp));
            }else{
                patt=Pattern.compile(operatorExp);
                mat=patt.matcher(expression);

                if(mat.find()){
                    String tempMinExp=mat.group();
                    expression=expression.replaceFirst(operatorExp, parseExp(tempMinExp));
                }
            }
            return parseExp(expression);
        }

        String minParentheses="\\([^\\(\\)]+\\)";
        Pattern patt=Pattern.compile(minParentheses);
        Matcher mat=patt.matcher(expression);

        if(mat.find()){
            String tempMinExp=mat.group();
            expression=expression.replaceFirst(minParentheses, parseExp(tempMinExp));
        }

        return parseExp(expression);
    }

    private static String calculate(String exp){
        exp=exp.replaceAll("[\\[\\]]", "");
        String number[]=exp.replaceFirst("(\\d)[\\+\\-\\*\\/]", "$1,").split(",");
        BigDecimal number1=new BigDecimal(number[0]);
        BigDecimal number2=new BigDecimal(number[1]);
        BigDecimal result=null;

        String operator=exp.replaceFirst("^.*\\d([\\+\\-\\*\\/]).+$", "$1");

        if("+".equals(operator)){
            result=number1.add(number2);
        }else if("-".equals(operator)){
            result=number1.subtract(number2);
        }else if("*".equals(operator)){
            result=number1.multiply(number2);
        }else if("/".equals(operator)){
            result=number1.divide(number2);
        }

        return result!=null?result.toString():null;
    }
    //[REF_END][http://www.2cto.com/kf/201207/142436.html]
}


output:
4.0
------ For reference only --------------------------------- ------
algorithm quoted from
http://www.2cto.com/kf/201207/142436.html

reprint please indicate the source
------ For reference only ---------------------------- -----------
should be able to use regular , but I can not write

没有评论:

发表评论