Структура данных для составления постфиксного выражения

Question

Привет! Я пишу rpn калькулятор на C и хочу скомпилировать выражение rpn в байт-код. Но я не уверен, что будет структура данных, чтобы представлять их ??? Моя структура данных стека до сих пор

 struct stack_t{
        int type;
        union {  
              double val;
              char *str;
              /* probably some more */
             }u;
    };

Answer 1

На самом деле это во многом зависит от набора функций, которые вы собираетесь поддерживать. Например, если ваш калькулятор поддерживает целые числа (например, целочисленное деление), вам, вероятно, понадобится int в вашем объединении.

Answer 2

Я прошел несколько переписываний интерпретатора postscript, и хотя моя структура объектов начиналась точно так же, как ваша, я в итоге обнаружил, что этот макет «лучше» по причинам, которые я не могу сформулировать. Я нашел эту идею в структуре событий X11.

typedef struct {
    word tag;
    word pad;
    dword padw;
} mark_;

typedef struct {
    word tag;
    word pad;
    integer val;
} int_;

typedef struct {
    word tag;
    word pad;
    real val;
} real_;

typedef struct {
    word tag;
    word sz;
    word ent;
    word off;
} comp_;

typedef union {
    word tag;

    mark_ mark_;
    int_ int_;
    real_ real_;
    comp_ comp_;
} object;

Может показаться избыточным наличие тега как снаружи, так и внутри каждой структуры, но он хранит все в милых маленьких коробочках. Это позволяет видеть схему памяти более четко.

Редактировать: я называю это «тег» вместо «тип», потому что он содержит и t ype и fl ag s.

---

Редактировать: Одна из причин, по которой я считаю это лучше , заключается в том, что он исключает термин .u из выражений доступа. Вместо stk.u.val у вас есть stk.real_.val или stk.int_.val. Часть union смещена в восходящем направлении, поэтому части данных могут иметь внутреннюю структуру без дополнительного вложения. И tag все еще доступен на верхнем уровне, чтобы определить, какой подтип используется.

Answer 3

Преимущество байт-кода RPN заключается в том, что его не нужно хранить в специальной структуре. Подойдет массив / вектор / список. Вам нужен стек для интерпретации этого, но для хранения программы вам нужно только преобразовать каждый токен в инструкцию байт-кода.

Что касается типов, добавляемых в ваш союз, это действительно зависит от семантики вашего калькулятора. Почему вы хотите иметь возможность хранить строки? Планируете ли вы использовать строгую типизацию?

Посмотрите на Forth , канонический простой язык RPN.