Лаба 12

#include <iostream>
#include <string>
#include <sstream>
#include <map>

template<class T>
struct Node {
    T value;
    Node *next;

    Node(T value, Node *next = nullptr)
            : value(value), next(next) {}
};

template<class T>
struct Stack {
    Node<T> *top;

    Stack() : top(nullptr) {}

    void push(T value) {
        this->top = new Node<T>(value, this->top);
    }

    T *pop() {
        T *value = this->peek();
        if (this->top != nullptr)
            this->top = this->top->next;
        return value;
    }

    T *peek() {
        return this->top == nullptr
               ? nullptr
               : &this->top->value;
    }

    size_t size() {
        size_t size = 0;
        for (Node<T> *current = this->top; current != nullptr; size++, current = current->next);
        return size;
    }

    bool empty() {
        return this->top == nullptr;
    }

    std::string toString() {
        std::ostringstream sout;
        sout << '[';
        Node<T> *current = this->top;
        for (; current != nullptr && current->next != nullptr; current = current->next)
            sout << current->value << ", ";
        if (current != nullptr)
            sout << current->value << ']';
        return sout.str();
    }
};

using namespace std;

int main() {
    Stack<string> operations;
    map<string, int> precedence {
        pair("(", 1),
        pair("+", 2), pair("-", 2),
        pair("*", 3), pair("/", 3)
    };

    string expression;

    cout << "Enter an expression: " << endl;

    getline(cin, expression);

    istringstream input(expression);
    ostringstream output;

    while (!input.eof()) {
        string token;
        input >> token;

        if (token == "+" || token == "-" || token == "*" || token == "/") {
            for (string *op = operations.peek(); op != nullptr; operations.pop(), op = operations.peek()) {
                if (precedence[*op] < precedence[token]) {
                    break;
                }
                output << *op << ' ';
            }
            operations.push(token);
        } else if (token == "(") {
            operations.push(token);
        } else if (token == ")") {
            for (string *op = operations.pop(); op != nullptr && *op != "("; op = operations.pop())
                output << *op << ' ';
        } else {
            output << token << ' ';
        }
    }

    for (string *op = operations.pop(); op != nullptr; op = operations.pop()) {
        output << *op << ' ';
    }

    cout << output.str() << endl;

    return 0;
}