Modeling Các Shunting-Yard Algorithm

Question

Bối cảnh:

Tôi cố gắng để thực hiện một biến thể của Shunting-Yard Algorithm, nhưng thay vì xuất ra các biểu hiện trong ký hiệu RPN, tôi muốn nó để cập nhật chính nó như là thẻ được đẩy trong quá kết quả có thể được hiển thị trong thời gian thực (như thể bạn đang nhấn các nút trên máy tính và cần cập nhật màn hình sau mỗi nút).

Đây là lớp Shunting-Yard ...

public class ShuntingYard 
{ 
    private Stack<double> _operands; 
    private Stack<Operation> _operations; 

    public ShuntingYard() 
    { 
     this._operands = new Stack<double>(); 
     this._operations = new Stack<double>(); 
    } 
} 

Và lớp Operation sẽ là một cái gì đó giống như ...

public abstract class Operation 
{ 
    public abstract void Evaluate(Stack<double> operands, Stack<Operation> operations); 
} 

Chức năng Evaluate() cập nhật các ngăn xếp cho phù hợp, và " giá trị hiện tại "sẽ là _operands.Peek()

Dưới đây là một số" Thao tác "tôi có cho đến thời điểm này:

public class NullaryOperation : Operation { }
Ví dụ: Pi, e vv
Chỉ cần đẩy liên tục vào _operands

public class UnaryOperation : Operation { }
Ví dụ: Căn bậc hai, Sine, Cosine vv
Pops một số tắt của _operands, đánh giá, và đẩy dẫn đến _operands

public class BinaryOperation : Operation { }
Ví dụ: +, -, *, /, vv
Kiểm tra ưu tiên, đánh giá nếu cần thiết, đẩy dẫn đến _operands

---

Đây là vấn đề:
tôi cần khả năng đẩy mở ngoặc ( và closed- dấu ngoặc đơn ) lên ngăn xếp _operations như là một phần của thuật toán. Hơn nữa, khi tôi thêm một dấu ngoặc đơn, tôi cần phải giữ các toán hạng/hoạt động popping cho đến khi tôi gặp phải một dấu ngoặc đơn mở.

Tôi muốn tránh kiểm tra như thế này (loại kiểm tra đối tượng):

while (operations.Peek().GetType() != typeof(OpenParen)) { ... }

Tôi muốn tránh thêm một phương pháp như thế này trong Operation:

public abstract bool IsOpenParen();

tôi có thể làm một cái gì đó như thế này ...

public abstract class Operation 
{ 
    public enum OperationType { Nullary, Unary, Binary, OpenParen, CloseParen }; 
    public abstract OperationType GetOperationType() { }; 

    public abstract void Evaluate(Stack<double> operands, Stack<Operation> operations); 
} 

Nhưng yêu cầu tất cả các kiểu con để chỉ định kiểu của chúng như là một enum có vẻ giống như một thiết kế xấu.

---

Làm cách nào để tôi có thể theo dõi và xử lý dấu ngoặc đơn khi chúng được đẩy vào?

Lưu ý: Suy nghĩ về dấu ngoặc đơn là "Hoạt động" dường như không có ý nghĩa gì đối với tôi. Tuy nhiên, thuật toán trên Wikipedia đối xử với họ theo cách này, và tôi không thể nghĩ ra bất kỳ cách nào khác để theo dõi vị trí của họ liên quan đến các hoạt động "thực sự" khác.

Cảm ơn bạn.

Answer 1

public class Operand { 
    private ShuntingYard sy; 
    private double d; 
    public Operand(double v) { 
     d=v; 
     sy=null; 
    } 
    public Operand() { 
     d=NaN(); // I'm inept at C#, this should mean "d" is unused 
     sy=new ShuntingYard(); 
    } 
} 
public class ShuntingYard { 
    private Stack<Operand> _operands; 
    private Stack<Operation> _operations; 

    public ShuntingYard() 
    { 
     this._operands = new Stack<Operand>(); 
     this._operations = new Stack<Operation>(); 
    } 
} 

StarPilot đưa ra một lời khuyên đúng, đặt ShuntingYard khác vào ngăn xếp, nhưng cách chính xác là để đặt một ShuntingYard như một toán hạng, không phải là phẫu thuật. Bây giờ, khi một lồng nhau ShuntingYard xuất hiện, tất cả toán hạng và thao tác tiếp theo sẽ được truyền cho nó. Một sự chuẩn bị cần được thực hiện để cho một ShuntingYard để nhận được một đóng ngoặc đơn hoạt động, một cấp cao nhất nên ném một lỗi, và những cái bên trong nên đánh giá bản thân và thay thế có chứa Operand với kết quả đánh giá của nó.