从 token 流解析表达式

Question

我正在尝试解析一种简单脚本语言的表达式，但我很困惑。现在，只有数字和字符串文字可以解析为表达式:

int x = 5;
double y = 3.4;
str t = "this is a string";

但是，我对解析更复杂的表达式感到困惑:

int a = 5 + 9;
int x = (5 + a) - (a ^ 2);

我想我会像这样实现它:

do {
    // no clue what I would do here?        

    if (current token is a semi colon) break;
}
while (true);

任何帮助都会很棒，我不知道从哪里开始。谢谢。

编辑:
我的解析器是一个递归下降解析器

我的表达“类”如下:

typedef struct s_Expression {
    char type;
    Token *value;

    struct s_Expression *leftHand;
    char operand;
    struct s_Expression *rightHand;
} ExpressionNode;

有人提到递归下降解析器能够在不做中缀的情况下解析表达式，到后缀。最好，我想要这样的表达式:

例如这个:

int x = (5 + 5) - (a / b);

将被解析为:
注意:这不是有效的 C，这只是一些伪代码，可以简单地表达我的观点:)

ExpressionNode lh;
lh.leftHand = new ExpressionNode(5);
lh.operand = '+'
lh.rightHand = new ExpressionNode(5);

ExpressionNode rh;
rh.leftHand = new ExpressionNode(a);
rh.operand = '/';
rh.rightHand = new ExpressionNode(b);

ExpressionNode res;
res.leftHand = lh;
res.operand = '-';
res.rightHand = rh;

我在深夜问了这个问题，很抱歉，如果我不清楚并且我完全忘记了我最初的目标是什么。

Answer 1

有多种方法可以做到这一点。我过去使用的一种方法是读取输入字符串(即编程语言代码)并将表达式从中缀转换为反向抛光表示法。这是一篇关于这样做的非常好的帖子:

http://andreinc.net/2010/10/05/converting-infix-to-rpn-shunting-yard-algorithm/

请注意 =也是一个运算符，因此您的解析应该真正包括整个代码文件，而不仅仅是某些表达式。

一旦进行反向抛光，表达式就非常容易评估。您只需弹出堆栈，随时存储操作数，直到遇到运算符。根据运算符(operator)的要求从堆栈中弹出尽可能多的操作数并执行您的操作。