Преобразование из Infix в Postfix с использованием стеков (C++)

Question

В настоящее время я работаю над проектом для преобразования из postfix в infix с использованием стека в виде отдельного списка. Мне удалось преобразовать выражения, такие как ab+, в (a+b), однако, когда выражение становится длиннее, например ab+cd*-. Это не работает. Я рассматриваю возможность перевода ранее преобразованного выражения обратно в стек, но стек имеет тип char, а выражение - это строка, и он жалуется, когда я пытаюсь его оттолкнуть. Должен ли я сделать его шаблоном, и если да, то как бы я это сделал или есть еще что-нибудь, чтобы решить эту проблему.

Вот мой код:

#include "stack.h" 

void convert(string expression){ 
    stack c; 
    string post = " "; 
    string rightop = ""; 
    string leftop = ""; 
    string op = ""; 

    for (int i = 0; i <= expression.length(); i++){ 
     c.push(expression[i]); 
     c.print(); 
     if (expression[i] == '*' || 
      expression[i] == '+' || 
      expression[i] == '-' || 
      expression[i] == '/'){ 
      cout << c.top() << endl; 
      leftop = c.top(); 
      cout << leftop << endl; 

      c.pop(); 

      rightop = c.top(); 
      cout << rightop << endl; 
      c.pop(); 
      op = c.top(); 
      cout << op << endl; 
      //c.pop(); 
      post = "(" + leftop + " " + op + " " + rightop + ")"; 

      cout << post << endl; 
     } 
     //c.push(post); 
    } 
} 


int main(){ 
    string expression; 
    cout << " Enter a Post Fix expression: ";  
    getline(cin, expression);  
    convert(expression);  
    return 0; 
} 

Answer 1

Исходный код отсутствует следующие объявления компиляции:

#include "stack" 
#include "string" 
#include "iostream" 

using namespace std; 

Далее, тип стека должен быть string, чтобы иметь возможность хранить полный выражения на нем.

Вы не брали элементы в правильном порядке из стека: это первый op, следующий rightop и, наконец leftop

в настоящее время закомментирована последний c.pop() необходимо удалить 3-й элемент из стека, но должны следовать внутри цикла с (опять закомментирована) c.push(post);

петля на expression идет один шаг слишком далеко: он должен быть for (int i =0; i<expression.length();i++) (обратите внимание на < вместо <=)

Когда это будет сделано, то достаточно, чтобы сделать функцию convert вернуть последнюю post в виде строки для программы, чтобы дать ожидаемый результат.

Как вы просили в этом other question, было бы намного лучше игнорировать пробелы во входной строке: вы должны добавить if (isspace(expression[i])) continue; сразу после for.

Со всеми этими исправлениями, код может быть:

#include <stack> 
#include <string> 
#include <iostream> 
#include <cctypes> 

using namespace std; 

string convert(string expression){ 

    stack<string> c; 

    string post =" "; 
    string rightop=""; 
    string leftop=""; 
    string op =""; 

    for (int i =0; i<expression.length();i++){ 
     if (isspace(expression[i])) continue; 
     c.push(string(expression.c_str() + i, 1)); 
     //c.print(); 
     if(expression[i] == '*' || 
      expression[i] == '+' || 
      expression[i] == '-' || 
      expression[i] == '/'){ 
       cout<<c.top()<<endl; 
       op=c.top(); 
       cout<<leftop<<endl; 

       c.pop(); 


       rightop=c.top(); 
       cout<<rightop<<endl; 
       c.pop(); 
       leftop=c.top(); 
       cout<<op<<endl; 
       c.pop(); 
       post="(" + leftop + " " + op + " " + rightop + ")"; 

       cout<<post<<endl; 
       c.push(post); 
     } 
    } 
    return post; 
} 

int main(){ 

    string expression; 
    cout<<" Enter a Post Fix expression: "; 

    getline(cin,expression); 

    string converted = convert(expression); 

    cout << "Converted expression : " << converted << endl; 

    return 0; 
} 

И когда дано ab+cd*- вы получите в конце ((a + b) - (c * d))

Вы просто должны закомментировать все следы образуют преобразования метод ;-)

Answer 2

У меня создается впечатление, что ваш «стек» не используется должным образом. например если абы + * выталкиваются в стеке ваш переменные становится leftop = +, rightop = b, op = a для того, чтобы преобразовать выражение постфикса это легче всего создать бинарное дерево оценки для получения Оператора старшинства права

например

для аб + с * Вы хотите

 * 
    /\ 
    + c 
/\ 
a b 

, а затем оценить дерево либо рекурсивно или нет.каждый раз оператор + или - используйте вокруг него круглые скобки,