使用递归对前缀转换的Infix

Question

我很难找到前缀翻译方案。

I已计算出修复后的翻译剪键:

expr -> Term, Rest
Rest -> +Term, { print('+') } , Rest | -Term, { print('-') }, Rest | epsilon
Term -> Factor, Rest_
Rest_ -> *Factor, { print('*') }, Rest_ | /Factor, { print('/') }, Rest_ | epsilon
Factor -> Digit | (expr)
Digit -> 0,1,2,3,4,5,6,7,8,9

根据上面的翻译方案，和postfix到后缀的转换代码:

#include<iostream>

using namespace std;

const char input[] = "9-5*2";
int index = 0;
char LookAhead = input[index];

void Match(char newChar);
void Factor();
void Rest_();
void Rest();
void Term();
void Expression();


int main(){
    Expression();
    return 0;
}

void Match(char newChar){
    if(newChar == LookAhead){
        index++;
        LookAhead = input[index];
    }
}

void Expression(){
    Term();
    Rest();
}

void Term(){
    Factor();
    Rest_();
}

void Rest(){
    if(LookAhead == '+'){
        Match('+');
        Term();
        cout << '+';
        Rest();
    }else if(LookAhead == '-'){
        Match('-');
        Term();
        cout << '-';
        Rest();
    }else{

    }
}

void Rest_(){
    if(LookAhead == '*'){
        Match('*');
        Factor();
        cout << '*';
        Rest_();
    }else if(LookAhead == '/'){
        Match('/');
        Factor();
        cout << '/';
        Rest_();
    }else{

    }
}

void Factor(){
    if(isdigit(LookAhead)){
        cout << LookAhead;
        Match(LookAhead);
    }
}

所以现在有任何专家可以帮助我理解从前缀到前缀转换的翻译方案，我们将不胜感激。

我们可以通过解析树进行测试。如果我们可以生成类似-9+52前缀字符串的示例字符串9-5+2。

告诉我是否需要解释更多关于我的infix to postfix转换方案和代码，以获得更好的理解。

提前谢谢！

编辑: --我很难找到前缀表达式转换方案。举个例子，我的意见：

9-5+2

预期产出：

-9+52

我想要用上面所示的从infix到后缀转换的结构来实现这一点。仅此而已！

Answer 1

最简单的解决方案是在解析时构造一个抽象语法树(AST)，然后使用预序导线递归地遍历树。

您也可以在运行时构造字符串(例如，如建议的这里是@ChrisDodd )，但是：

• 这不是一个递归的解决方案:)
• 它涉及大量的字符串复制，因此它可能有二次运行时间。

还可能会尝试将后缀转换为某种临时数据结构(例如，堆栈)，然后通过打印前缀表达式递归地遍历后缀表示“计算”。这当然会起作用，但您会遇到这样的问题:以自然的方式遍历后缀表示将首先访问每个表达式的右参数，而您首先想要的是左边的参数。这意味着您需要向后构造字符串，这涉及另一个临时数据结构(例如，另一个堆栈)。

总的来说，AST解决方案更干净，为以后添加更多功能提供了良好的基础。

Answer 2

因此，我使用一个时态变量来存储我的数字，并递归地检查和打印操作符，以保持订单的优先级。

我的解决方案：

#include<iostream>

using namespace std;

const char input[] = "9-5+2";
int index = 0;
char LookAhead = input[index];
char TempLookAhead = 'x';

void Match(char newChar);
void Factor();
void Rest_();
void Rest();
void Term();
void Expression();


int main(){
    Expression();
    return 0;
}

void Match(char newChar){
    if(newChar == LookAhead){
        index++;
        LookAhead = input[index];
    }
}

void Expression(){
    Term();
    Rest();
    cout << TempLookAhead;
}

void Term(){
    Factor();
    Rest_();
}

void Rest(){
    if(LookAhead == '+'){
        cout << '+';
        cout << TempLookAhead;
        Match(LookAhead);
        Term();
        Rest();
    }else if(LookAhead == '-'){
        cout << '-';
        cout << TempLookAhead;
        Match(LookAhead);
        Term();
        Rest();
    }else{

    }
}

void Rest_(){
    if(LookAhead == '*'){
        cout << '*';
        cout << TempLookAhead;
        Match(LookAhead);
        Factor();
        Rest_();
    }else if(LookAhead == '/'){
        cout << '/';
        cout << TempLookAhead;
        Match(LookAhead);
        Factor();
        Rest_();
    }else{

    }
}

void Factor(){
    if(isdigit(LookAhead)){
        TempLookAhead = LookAhead;
        Match(LookAhead);
    }
}