#c #prefix #shunting-yard
#c #префикс #shunting-yard
Вопрос:
Я успешно реализовал алгоритм шунтирования в C для преобразования инфиксного выражения в постфиксное выражение (RPN). Мне нужно изменить свой алгоритм, чтобы вернуть префиксное (польское) выражение, и я не знаю как.
infixt(string s) {
infixExpression = s;
string temp;
stack = new Stack();
for (int i = 0; i < infixExpression.length(); i ) {
if (infixExpression[i] != ' ') {
temp = s[i];
} else {
if (isOperator(temp[0])) {
while(!stack->isEmpty() amp;amp; stack->top().toString().c_str()[0] != '(' amp;amp; isHigherPrecedence(stack->top().toString().c_str()[0], temp[0])) {
StackItem item = stack->top();
prefixExpression = item.toString() " ";
stack->pop();
}
StackItem *item = new StackItem(temp);
stack->push(*item);
} else if (isOperand(temp[0])) {
prefixExpression = temp " ";
} else if (temp[0] == '(') {
StackItem *item = new StackItem(temp);
stack->push(*item);
} else if (temp[0] == ')') {
while (!stack->isEmpty() amp;amp; stack->top().toString().c_str()[0] != '(') {
StackItem item = stack->top();
prefixExpression = item.toString() " ";
stack->pop();
}
stack->pop();
}
temp = "";
}
}
while (!stack->isEmpty()) {
StackItem item = stack->top();
prefixExpression = item.toString() " ";
stack->pop();
}
prefixExpression = " ;";
}
Комментарии:
1. Просто переверните постфикс.
Ответ №1:
Для преобразования инфикса в префикс:
1 —> Измените выражение инфикса на обратное (обработайте порядок скобок при обратном. Пример: Допустим, вы хотите отменить это выражение -> «(a b) c» если вы измените это, не упорядочивая круглые скобки, это даст вам это -> «c) b a (» поэтому вам нужно упорядочить круглые скобки.)
2 -> Применить постфиксную нотацию к обращенному выражению инфикса (при применении алгоритма шунтирования, если приоритет вершины стека операторов и приоритет текущего оператора равны, не открывайте стек операторов, просто вставьте текущий оператор в стек операторов и продолжайте.)
3 —> Снова измените выражение, и оно даст вам префиксное обозначение исходного инфиксного выражения.