Как конвертировать инфикс в постфиксное выражение в стеке C ++

Question

Я создаю программу на ООП C ++, которая преобразует Infix в выражение Postfix, используя предопределенные классы Stackitem и Stack (эти два класса работают нормально). Но у меня есть некоторые проблемы в реализации алгоритма преобразования. Я не могу получить ожидаемый результат для некоторых входов.

Я попытался реализовать следующий алгоритм:

Основные шаги при разборе выражения инфикса:

• , если элемент является операндом, немедленно вывести
• если элемент является левой круглой скобкой, поместите в стек
• , если элемент является правой круглой скобкой, вытолкните стек и выводите содержимое до левой круглой скобки (скобка вставлена, но не выводится)
• если элемент является оператором, вытолкните и выведите все операторы с более высоким или равным приоритетом, затем поместите элемент в стек
• просто поместите элемент в стек, если стек пуст иливерхний элемент является левой круглой скобкой или если верхний элемент имеет более низкий приоритет.

Реализация класса Stackitem, которая помогает в определении, является ли элемент оператором, операндом и его приоритетом (путем предоставления целого числа)

#include "StackItem.h"

StackItem::StackItem(bool isOp, int i) {
    init(isOp, i);
    next = 0;
}

StackItem::StackItem(string item) {
    if(item.compare("+") == 0)
        init(true, OPERATOR_PLUS);
    else if(item.compare("-") == 0)
        init(true, OPERATOR_MINUS);
    else if(item.compare("*") == 0)
        init(true, OPERATOR_MULTIPLICATION);
    else if(item.compare("/") == 0)
        init(true, OPERATOR_DIVISION);
    else if(item.compare("(") == 0)
        init(true, OPERATOR_LEFTPAR);
    else if(item.compare(")") == 0)
        init(true, OPERATOR_RIGHTPAR);
    else
        init(false, atoi(item.c_str()));
}

void StackItem::init(bool isOp, int i) {
    isOperator = isOp;
    if(isOp)
        op = i;
    else
        n = i;
}

string StackItem::toString() {
    stringstream ss;

    if(!isOperator) {
        ss << n;
    } else {
        switch(op) {
            case OPERATOR_MINUS:
                ss << "-";
                break;
            case OPERATOR_PLUS:
                ss << "+";
                break;
            case OPERATOR_DIVISION:
                ss << "/";
                break;
            case OPERATOR_MULTIPLICATION:
                ss << "*";
                break;
            case OPERATOR_LEFTPAR:
                ss << "(";
                break;
            case OPERATOR_RIGHTPAR:
                ss << ")";
                break;
        }
    }
    return ss.str();
}

А вот и проблемный код (для конвертации). Я подозреваю, что проблема связана с моей (пятая и шестая точка шагов алгоритма)

#include "Calculator.h"
#include <iostream>

Calculator::Calculator( string expression ) {
    infixExpression = expression;
    stack = new Stack();
    istringstream iss( expression );
    string token;
    iss >> token;
    postfixExpression = "";

    while ( token.compare( ";" ) != 0 ) {
        cout << "token:" << token << endl;
        StackItem *item = new StackItem( token );

        if ( !item->isOperator ) {
            postfixExpression += item->toString() + " ";
        } else {
            if ( item->op == OPERATOR_LEFTPAR )
                stack->push( item );
            else if ( item->op == OPERATOR_RIGHTPAR ) {
                while ( !stack->isEmpty() && stack->top() != OPERATOR_LEFTPAR ) {
                    string s = stack->top()->toString();
                    delete stack->pop();
                    postfixExpression += s + " ";

                }
                string s = stack->top()->toString();
                delete stack->pop();
            } else {
                while ( !stack->isEmpty() && ( item->op <= stack->top()->op ) ) {
                    if ( stack->top()->isOperator ) {
                        string s = stack->top()->toString();
                        delete stack->pop();
                        postfixExpression += s + " ";
                    }
                    break;
                }
                while ( ( stack->isEmpty() ) || ( stack->top()->op == OPERATOR_LEFTPAR ) || ( stack->top()->op < item->op ) ) {
                    stack->push( item );
                }
            }
        }
        iss >> token;
    }

    while ( !stack->isEmpty() ) {
        string s = stack->top()->toString();
        delete stack->pop();
        postfixExpression += s + " ";
    }

    postfixExpression += ";";
}

string Calculator::getPostfix() {
    return postfixExpression;
}

Необходимые входы и выходы должны быть проанализированы в соответствии с ";"в конце и между каждой входной и выходной частью должен оставаться пробел. Пример:

Ввод: 1 + 2 + 3;

Ввод: 1 2 + 3 +;(это прекрасно работает)

Однако, вход: (1 + 2);

Выход: ничего (возвращает возвращаемый адрес памяти)

Также для: Вход: 10+ 10 * 40 - 45/5;

Выход: 10 10 4 * 45 5 / +;

Неверный порядок!

Редактировать: Оператор определяет:следующим образом:

#define OPERATOR_LEFTPAR        0
#define OPERATOR_RIGHTPAR       1
#define OPERATOR_MINUS          2
#define OPERATOR_PLUS           3
#define OPERATOR_DIVISION       4
#define OPERATOR_MULTIPLICATION 5

Редактировать: Этот новый код решил много проблем с базовыми и короткими входами, все еще очень большие и сложные выражения вылетали на выходе.

#include "Calculator.h"
#include <iostream>

Calculator::Calculator(string expression)
{

    infixExpression=expression;
    stack = new Stack();
    istringstream iss(expression);
    string token;
     iss >> token;
     postfixExpression="";

    while(token.compare(";") != 0)
    {
        //cout << "token:"<<token << endl;
        StackItem* item=new StackItem(token);

        if(!item->isOperator){
            postfixExpression += item->toString() + " ";

        }
         else
        {
            if(item->op == OPERATOR_LEFTPAR)
                    stack->push(item);
            else if(item->op == OPERATOR_RIGHTPAR)
            {
                while(!stack->isEmpty()&& stack->top()->op != OPERATOR_LEFTPAR)
                {
                    string s = stack->top()->toString();
                    delete stack->pop();
                    postfixExpression +=s+" ";

                }

                string s = stack->top()->toString();
                delete stack->pop();
            }
            else
            {
                while((!stack->isEmpty()) && item->op <= stack->top()->op)
                {
                     string s = stack->top()->toString();
                     delete stack->pop();
                     postfixExpression +=s+" ";

                }

                while((stack->isEmpty()) || item->op > stack->top()->op || stack->top()->op==OPERATOR_LEFTPAR)
                {
                    stack->push(item);
                }


            }

        }
        iss >> token;
    }


    while(!stack->isEmpty())
    {

         string s = stack->top()->toString();
        delete stack->pop();
        postfixExpression +=s+" ";
    }

    postfixExpression += ";";
}



string Calculator::getPostfix()
{



     return postfixExpression;

}