chức năng đánh giá Viết Chuỗi

Question

Tôi đang cố gắng để viết một hàm Chuỗi thẩm định ví dụ:

evaluate("4 + 1") ; // returns 5 
evaluate("4 + 1 + 3") ; // returns 8 
evaluate("4 + 1 * 3") ; // returns 7 (not 15) 

The operators are + -/and * 

My ban đầu mặc dù đã sử dụng biểu thức thông thường để thu thập các nhà khai thác và chữ số vì chúng có thể được xuất hiện. Và hơn sau khi tìm thấy thông tin đó, bằng cách nào đó, hãy tìm ra cách ưu tiên các nhà điều hành /* ove -+.

Dưới đây là cách tôi bắt đầu:

static String regex = "([\\+\\*-/])+"; 
static String digitRegex = "(\\d)+"; 

public static void main(String[] args) { 
    System.out.println(getOperators("4 + 1 * 3")); 
} 

public static List<String> getOperators(String input) { 
    Pattern p = Pattern.compile(regex); 
    Matcher matcher = p.matcher(input); 

    List<String> operatorList = new ArrayList<String>(); 

    int count = 0; 
    while (matcher.find()){ 
     if (matcher.group(count) != null && matcher.group(count).trim().length() > 0) { 
     operatorList.add(matcher.group(count)); 
     count++; 
     } 
    } 

    return operatorList; 
} 

Bây giờ tôi có thể viết một phương pháp để trích xuất các chữ số bằng cách sử dụng cùng một logic.

public static List<Integer> getDigits(String input) { 
     Pattern p = Pattern.compile(digitRegex); 
     Matcher matcher = p.matcher(input); 

     List<Integer> digitList = new ArrayList<Integer>(); 

     int count = 0; 
     while (matcher.find()) { 
      if (matcher.group(count) != null && matcher.group(count).trim().length() > 0) { 
       digitList.add(Integer.valueOf(matcher.group(count))); 
       count++; 
      } 
     } 

     return digitList; 
    } 

Bây giờ là phần tôi bị kẹt. # 1 Phương pháp trên không thành công trên ví dụ thứ ba:

evaluate("4 + 1 * 3") ; // returns 7 (not 15) 

Và # 2 Ngay cả khi tôi thử các ví dụ trước, tôi không thể hiểu được cách đặt đúng thứ tự.

Tôi có đi đúng hướng không, có ai có lời khuyên hữu ích nào vui lòng chia sẻ không?

Answer 1

Tôi đã viết ở đây một cái gì đó ... giả sử rằng nhanh chóng & bẩn là một cách nói ...
Bằng mọi cách, bạn KHÔNG nên sử dụng nó "nguyên trạng". Nó cần "sửa chữa" - việc đọc các số/phép tính số học nên được thực hiện bằng cách sử dụng StringTokenizer - nhưng tôi sẽ để lại các kỹ thuật cho bạn;)

public class NewClass { 

    public static int evaluate(String str){ 
     if("".equals(str)){ 
      return 0; 
     } 
     else if(str.length() == 1){ 
      return Integer.valueOf(str); 
     } 
     else{ 
      String _a = String.valueOf(str.charAt(0)); 
      String _b = String.valueOf(str.charAt(1)); 
      if("+".equals(_b) || "-".equals(_b)){ 
       if("+".equals(_b)){ 
        return Integer.valueOf(_a) + evaluate(str.substring(2)); 
       } 
       else{// "-" 
        return Integer.valueOf(_a) - evaluate(str.substring(2)); 
       } 
      } 
      else{// "*" or "/" 
       boolean isMulti = ("*".equals(_b)); 
       String _c = String.valueOf(str.charAt(2));     
       Integer tmp = 0; 
       if(isMulti){ 
        tmp = Integer.valueOf(_a) * Integer.valueOf(_c); 
       } 
       else{ 
        tmp = Integer.valueOf(_a)/Integer.valueOf(_c); 
       } 
       String new_str = String.valueOf(tmp) + str.substring(3);     
       return evaluate(new_str); 
      } 
     } 
    } 

    public static void main(String[] args){   
     String e = "4+1*3"; 
     int t = evaluate(e); 
     System.out.println(e + " = "+t); 
    } 

} 

Answer 2

Bạn muốn có một operator precedence parser. Đây là một trình phân tích cú pháp dựa trên bảng rất phổ biến được thiết kế để thực hiện chính xác những gì bạn muốn. Về cơ bản, bạn so sánh toán tử được quét với một toán tử ở trên cùng của ngăn xếp và chọn giảm ngăn xếp (nghĩa là, thực hiện phép toán và đẩy kết quả trở lại trên ngăn xếp) hoặc đẩy toán tử.

Là phần thưởng bổ sung, OPP dễ dàng và thú vị để viết. Bạn có thể thêm hỗ trợ cho dấu ngoặc đơn vv với ít nỗ lực bổ sung.

chỉnh sửa - Tôi vừa đọc bài viết wiki đó. Thật khủng khiếp.

Tìm các ví dụ khác về loại trình phân tích cú pháp này.

Chỉnh sửa 2 -

This one shows a sample in c. Note the table.

This one is pretty good.

Và hãy nhớ, bạn đang hỗ trợ một số ít các nhà khai thác, do đó, không được sợ hãi. bên cạnh đó, tất cả đều giống nhau khi bạn thực hiện một bảng.