Преобразование инфикса в префикс с использованием рекурсии
Я изо всех сил пытаюсь найти схему перевода префикса инфикса.
Я понял, что инфикс для постфикса перевода:
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
И мой код преобразования инфикса в постфикс в соответствии с приведенной выше схемой перевода:
#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 .
Скажите мне, если мне нужно больше рассказать о моей схеме преобразования и преобразования префиксов в инфиксы в постфиксы, чтобы лучше понять.
Заранее спасибо !
Отредактировано:
просто у меня проблема с поиском схемы преобразования преобразования префикса в инфикс в префикс. В качестве примера,
Мой вклад:
9-5+2
Ожидаемый результат:
-9+52
И я хочу добиться этого с той же структурой, которую я показал выше, с преобразованием из инфикса в постфикс.
Это все !
Решение
Самое простое решение состоит в том, чтобы построить Абстрактное синтаксическое дерево (AST) в то время как вы анализируете, а затем рекурсивно ходить по дереву, используя предварительный ход.
Вы также можете построить строку, как вы идете (как предложено здесь @ChrisDodd, например), но:
- это не рекурсивное решение :), и
- он включает в себя много строк копирования, поэтому он, вероятно, будет иметь квадратичное время выполнения.
Также может показаться заманчивым сделать постфиксное преобразование во временную структуру данных (например, в стек), а затем рекурсивно пройтись по «оценке» постфиксного представления, напечатав выражение префикса. Это, безусловно, сработает, но вы столкнетесь с проблемой, заключающейся в том, что естественным образом пройдя представление постфикса, сначала посетите правая рука аргумент каждого выражения, тогда как в первую очередь вы хотите левая рука аргумент. Это означает, что вам нужно построить строку в обратном направлении, что включает в себя другую временную структуру данных (например, другой стек).
В целом решение AST является более чистым и обеспечивает хорошую основу для добавления дополнительных функций в будущем.
Другие решения
Поэтому я использовал временную переменную для хранения своих цифр и проверял и печатал рекурсивно операторы с сохранением приоритета заказов.
Мое решение:
#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);
}
}