Các vấn đề với thuật toán shunting yard

Question

Tôi đã triển khai thành công thuật toán shunting yard trong java. Các thuật toán chính nó là đơn giản tuy nhiên tôi gặp rắc rối với tokenizer. Hiện tại, thuật toán hoạt động với mọi thứ tôi muốn loại trừ một thứ. Làm thế nào tôi có thể biết sự khác biệt giữa phép trừ (-) và cực âm (-)

như 4-3 là trừ nhưng -4 + 3 là tiêu cực

bây giờ tôi biết làm thế nào để biết khi nào cần một tiêu cực và khi nó phải là một trừ, nhưng trong thuật toán nên nó được đặt bởi vì nếu bạn sử dụng nó như một chức năng nó sẽ không luôn luôn làm việc ví dụ

3 + 4 * 2/- (1 - 5)^2^3

khi 1-5 trở thành -4, nó sẽ trở thành 4 trước khi được bình phương và thu nhỏ

giống như 3 + 4 * 2/cos (1-5)^2^3, bạn sẽ mất cosin trước khi bình phương và Cubing

nhưng trong toán học thực sự bạn sẽ không phải với một - bởi vì những gì bạn thực sự nói là 3 + 4 * 2/- ((1 - 5)^2^3) để có giá trị phù hợp

Answer 1

Câu trả lời cho this question có thể hữu ích.

Cụ thể, một trong các câu trả lời đó tham chiếu solution trong C xử lý trừ đi một cách đơn nhất. Về cơ bản, bạn phải nhận ra một trừ đi đơn nhất dựa trên sự xuất hiện của dấu trừ ở vị trí mà một toán tử nhị phân không thể, và tạo một mã thông báo khác cho nó, vì nó có ưu tiên khác nhau.

Dijkstra's original paper không giải thích rõ ràng cách anh ta xử lý vấn đề này, nhưng trừ đi đơn vị được liệt kê là một toán tử riêng biệt.

Answer 2

Có vẻ như bạn đang thực hiện một trình phân tích cú pháp kiểu phân tích cú pháp, khi đó bạn sẽ cần một máy trạng thái đơn giản trong lexer để nhận các mã thông báo riêng biệt và trừ nhị phân. (Trong trình phân tích cú pháp PEG, đây không phải là điều bạn phải lo lắng.)

Trong JavaCC, bạn sẽ có trạng thái DEFAULT, nơi bạn sẽ xem - là UNARY_MINUS. Khi bạn mã hóa kết thúc biểu thức chính (dấu ngoặc đóng hoặc số nguyên, dựa trên ví dụ bạn đã cung cấp), thì bạn sẽ chuyển sang trạng thái INFIX, trong đó - sẽ được coi là INFIX_MINUS. Khi bạn gặp phải bất kỳ toán tử infix nào, bạn sẽ trở về trạng thái DEFAULT.

Nếu bạn đang cuộn của riêng mình, nó có thể là một chút đơn giản hơn thế. Hãy xem số Python code này để có cách làm thông minh. Về cơ bản, khi bạn gặp phải một số -, bạn chỉ cần kiểm tra xem mã thông báo trước đó có phải là toán tử infix hay không. Ví dụ đó sử dụng chuỗi "-u" để biểu thị mã thông báo trừ đơn nhất, thuận tiện cho việc mã thông báo không chính thức. Tốt nhất tôi có thể nói, ví dụ Python không xử lý trường hợp trong đó - theo sau dấu ngoặc mở, hoặc xuất hiện ở đầu đầu vào. Những người đó nên được coi là thống nhất.

Để thống kê trừ đi được xử lý chính xác trong thuật toán shunting-yard, nó cần phải có ưu tiên cao hơn bất kỳ toán tử nào, và nó cần được đánh dấu là liên kết phù hợp. (Hãy chắc chắn rằng bạn xử lý liên kết phải.Bạn có thể đã bỏ nó ra khỏi phần còn lại của các toán tử của bạn là liên kết bên trái.) Điều này là đủ rõ ràng trong mã Python (mặc dù tôi sẽ sử dụng một số loại struct hơn là hai bản đồ riêng biệt).

Khi có thời gian để đánh giá, bạn sẽ cần phải xử lý các toán tử đơn nhất một chút khác nhau, vì bạn chỉ cần bật một số ra khỏi ngăn xếp, thay vì hai. Tùy thuộc vào việc triển khai của bạn trông như thế nào, có thể dễ dàng hơn trong việc đi qua danh sách và thay thế mọi lần xuất hiện của "-u" bằng [-1, "*"].

Nếu bạn có thể làm theo Python, bạn sẽ có thể thấy mọi thứ tôi đang nói đến trong ví dụ mà tôi đã liên kết tới. Tôi thấy mã dễ đọc hơn phiên bản C mà người khác đã đề cập. Ngoài ra, nếu bạn tò mò, tôi đã viết một chút trong khi quay trở lại sử dụng shunting-yard in Ruby, nhưng tôi xử lý các toán tử đơn nhất như một nonterminal riêng biệt, vì vậy chúng không được hiển thị.

Answer 3

Trong lexer của bạn, bạn có thể thực hiện điều này pseudo-logic:

if (symbol == '-') { 
    if (previousToken is a number 
    OR previousToken is an identifier 
    OR previousToken is a function) { 
     currentToken = SUBTRACT; 
    } else { 
     currentToken = NEGATION; 
    } 
} 

Bạn có thể thiết lập phủ định để có một ưu tiên cao hơn nhân và chia, nhưng thấp hơn so với lũy thừa. Bạn cũng có thể thiết lập nó để được kết hợp đúng (giống như '^'). Sau đó, bạn chỉ cần tích hợp ưu tiên và tính tương thích vào thuật toán như được mô tả trên trang Wikipedia.

Nếu mã thông báo là một nhà điều hành, o1, sau đó: trong khi có một nhà điều hành token, o2, ở phía trên cùng của ngăn xếp, và một trong hai o1 được trái kết hợp và ưu tiên của nó là nhỏ hơn hoặc bằng với o2, hoặc o1 có ưu tiên nhỏ hơn o2, pop o2 ngoài ngăn xếp, vào đầu ra hàng đợi; đẩy o1 vào ngăn xếp.

tôi đã kết thúc thực hiện mã tương ứng này:

} else if (nextToken instanceof Operator) { 
    final Operator o1 = (Operator) nextToken; 

    while (!stack.isEmpty() && stack.peek() instanceof Operator) { 
     final Operator o2 = (Operator) stack.peek(); 

     if ((o1.associativity == Associativity.LEFT && o1.precedence <= o2.precedence) 
     || (o1.associativity == Associativity.RIGHT && o1.precedence < o2.precedence)) { 
      popStackTopToOutput(); 
     } else { 
      break; 
     } 
    } 

    stack.push(nextToken); 
} 

Austin Taylor là hoàn toàn đúng mà bạn chỉ cần bật tắt một số cho một toán tử đơn hạng:

if (token is operator negate) { 
    operand = pop; 
    push operand * -1; 
} 

dự án Ví dụ:

https://github.com/Digipom/Calculator-for-Android/

Đọc thêm:

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

http://sankuru.biz/blog/1-parsing-object-oriented-expressions-with-dijkstras-shunting-yard-algorithm

Answer 4

Tôi biết đó là một bài cũ, nhưng có thể ai đó sẽ tìm thấy nó hữu ích. Tôi đã triển khai thuật toán này trước đây, bắt đầu bằng toknizer sử dụng lớp StreamTokenizer và hoạt động tốt. Trong StreamTokenizer trong Java, có một số ký tự có ý nghĩa cụ thể. Ví dụ: (là một toán tử, sin là một từ, ... Đối với câu hỏi của bạn, Có một phương thức được gọi là "streamToknizer.ordinaryChar (..)" mà nó xác định rằng đối số ký tự là "bình thường" trong bộ mã thông báo này. Nó loại bỏ bất kỳ ý nghĩa đặc biệt nào của nhân vật như một nhân vật bình luận, thành phần từ, dấu tách chuỗi, khoảng trắng, hoặc ký tự số. một dấu hiệu cho số.Ví dụ: nếu bạn có biểu thức 2-3, Bạn sẽ có [2, -, 3], nhưng nếu bạn không chỉ định nó là bình thường, thì nó sẽ là [2, -3]