Необходимо создать инфикс для постфиксного алгоритма
Мне нужно реализовать алгоритм преобразования инфикса в постфикс, чтобы вычислить выражение a + b * c-d / e
Мне также нужно сделать это с помощью очереди (я считаю, что нужны 2 разных стека очереди)
Я создал свой класс очереди, используя DoubleLinkList, и теперь мне просто нужно создать алгоритм для этой проблемы. Хотя я довольно растерялся, как это сделать. Любая помощь будет оценена!
до сих пор (и я знаю, что это очень неправильно) у меня есть:
string infix = "a+b*c-d/e";
Queue *holder = new Queue();
Queue *newstring = new Queue();
int length = infix.length();
char temp;
char prev;
for(int i=0; i<length; i++)
{
temp = infix[i];
if((temp == '+') || (temp == '-') || (temp == '*') || (temp == '/'))
{
if (holder->isEmpty())
{
holder->queue(temp);
}
if(temp<holder.enqueue())
{
}
}
holder->queue(temp);
}
Решение
Я предполагаю, что это домашнее задание, поэтому важно, чтобы вы самостоятельно выяснили детали программирования. Общая схема алгоритма следующая:
Define a stack
Go through each character in the string
If it is between 0 to 9, append it to output string.
If it is left brace push to stack
If it is operator *+-/ then
If the stack is empty push it to the stack
If the stack is not empty then start a loop:
If the top of the stack has higher precedence
Then pop and append to output string
Else break
Push to the stack
If it is right brace then
While stack not empty and top not equal to left brace
Pop from stack and append to output string
Finally pop out the left brace.
If there is any input in the stack pop and append to the output string.
Другие решения
Я думаю, что вы должны создать дерево операторов и значений.
Вы можете конвертировать из инфикса в постфикс префикс в зависимости от вашего порядка обхода дерева.
Ваш инструктор может дать вам задание для конвертации между тремя.
Вот несколько статей:
Техасский университет
YouTube видео
Википедия — Выражение деревьев