Блог

Я успешно реализовал алгоритм шунтирования в 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 —> Измените выражение инфикса на обратное (обработайте порядок скобок при обратном. Пример: Допустим, вы хотите отменить это выражение -> «(a b) c» если вы измените это, не упорядочивая круглые скобки, это даст вам это -> «c) b a (» поэтому вам нужно упорядочить круглые скобки.)

2 -> Применить постфиксную нотацию к обращенному выражению инфикса (при применении алгоритма шунтирования, если приоритет вершины стека операторов и приоритет текущего оператора равны, не открывайте стек операторов, просто вставьте текущий оператор в стек операторов и продолжайте.)

3 —> Снова измените выражение, и оно даст вам префиксное обозначение исходного инфиксного выражения.