Algorytm C++ zamieniający np: cbrt(cbrt(23)) na (23^1/3)^1/3

Question

Witam,

Mam taki problem z algorytmem zamieniającym pierwiastki na potęgowanie. 

Np: cbrt(23) = 23^1/3

W kodzie poniżej program sobie radzi z takim czymś cbrt(23) i zwraca:

Podaj wyrazenie matematyczne: cbrt(23)
Zamienione wyrazenie: ((23)^(1/3))

 

Schody się zaczynają jak chce wykonać taki zabieg

cbrt(cbrt(23)) = (23^1/3)^1/3

Program to zamienia na takie coś:

Podaj wyrazenie matematyczne: cbrt(cbrt(23))
Zamienione wyrazenie: ((cbrt(23)^(1/3)))

Nawiasy dobrze wykonał natomiast zabrakło potęgi 1/3. Chce żeby ten algorytm mógł zamieniać jeszcze bardziej zagnieżdżone pierwiastki. Fajnie by było jakby można było mieszać np cbrt(sqrt(23)) i program powinien zwrócić: 

(23^1/2)^1/3.

Jeszcze chciałem zrobić to z dowolnym stopnie np root(n)[a] n - stopień |  a - liczba pierwiastkowana

Chce żeby to wszystko mogło się mieszać ze sobą i móc wpisywać zagnieżdżone pierwiastki.

Próbowałem i nic nie idzie, tylko takie proste zamienia.

Będę bardzo wdzięczny za pomoc :)

#include <iostream>
#include <string>

// Funkcja do zamiany zapisu pierwiastków na potęgi
std::string convertToPowerNotation(const std::string& expression) {
    std::string result;
    int level = 0;  // Poziom zagnieżdżenia

    for (size_t i = 0; i < expression.length(); i++) {
        char c = expression[i];

        if (c == '(') {
            level++;
            result += '(';
        } else if (c == ')') {
            level--;
            result += ')';
        } else if (level == 0 && c == 'c' && expression.find("cbrt(", i) == i) {
            size_t start = i + 5; // Przesunięcie na początek argumentu
            size_t end = expression.find(")", start);
            if (end != std::string::npos) {
                std::string argument = expression.substr(start, end - start);
                result += "((" + argument + ")^(1/3))";
                i = end; // Przesuwamy iterator za zamieniony fragment
            }
        } else if (level == 0 && c == 's' && expression.find("sqrt(", i) == i) {
            size_t start = i + 5; // Przesunięcie na początek argumentu
            size_t end = expression.find(")", start);
            if (end != std::string::npos) {
                std::string argument = expression.substr(start, end - start);
                result += "((" + argument + ")^(1/2))";
                i = end; // Przesuwamy iterator za zamieniony fragment
            }
        } else if (level == 0 && c == 'r' && expression.find("root(", i) == i) {
            size_t start = i + 5; // Przesunięcie na początek argumentu
            size_t end = expression.find(")", start);
            if (end != std::string::npos) {
                std::string argument = expression.substr(start, end - start);
                result += "(" + argument + ")^";
                i = end; // Przesuwamy iterator za zamieniony fragment
            }
        } else {
            result += c;
        }
    }

    return result;
}

int main() {
    std::string input;

    std::cout << "Podaj wyrażenie matematyczne: ";
    std::getline(std::cin, input);

    std::string convertedExpression = convertToPowerNotation(input);

    std::cout << "Zamienione wyrażenie: " << convertedExpression << std::endl;

    return 0;
}

Pozdrawiam,

Piotr Domański

Answer 1

https://en.wikipedia.org/wiki/Shunting_yard_algorithm

Comments

W tym przypadku shunting yard to przesada, bo wszystkie operacje jakie ma to zwykłe zagnieżdżone funkcje (`a(b(c(4)[e(f(5))]))`). Natomiast Twój link by się przydał gdyby miał infix operatory (`a+b`, `a(b(1)+c(2)*d(3))`) gdziekolwiek na wejściu.

Answer 2

Typowy ładny sposób robienia tego to z jakimś stosem - to znaczy, jak masz `cbrt(root(5)[sqrt(...)])`, to podczas parsowania `...` masz gdzieś stos składający się z cbrt, root(5), sqrt. To nie musi być stos stworzony ręcznie przez Ciebie - to może być po prostu rekursja (zamiast obecnego `level`), na przykład:

std::string convert(std::string &expression, int &n) { // n jest referencją
    // ...
    if (expression.find("root"() == n) {
        n += 5; // 'root('
        std::string stopien = convert(expression, n);
        n += 1; // '['
        std::string liczba = convert(expression, n);
        result += std::format("({})^(1/({}))", liczba, stopien);
    }

Innymi słowy, mając `root(COS)[COS2]`, rekurencyjnie wywołujesz funkcję żeby przekonwertować wszystko w `()` i drugi raz żeby przekonwertować wszystko w `[]`. W szczególności, zauważ że nie szukam `find(')')`.

(można to też potencjalnie łatwiej napisać używając string_view z starts_with zamiast stringi, n i find())

Comments

Napisałem coś takiego i działa, tylko mam problem z wyrażeniem root(n)[a], n - stopień pierwiastka, a - liczba pierwiastkowana. 

Wpisuje root(2)[3] i pisze mi: invalid format root.

Chce też żeby root obsługiwało też zagnieżdżone pierwiastki np root(4)[cbrt(sqrt(32-2))].

#include <iostream>
#include <string>
#include <cmath>
#include <stdexcept>

class ExpressionParser {
public:
    std::string parse(const std::string& expression) {
        this->expression = expression;
        this->index = 0;
        return parseExpression();
    }

private:
    std::string expression;
    size_t index;

    char peek() {
        if (index < expression.size()) {
            return expression[index];
        }
        return '\0';
    }

    char consume() {
        if (index < expression.size()) {
            return expression[index++];
        }
        return '\0';
    }

    std::string parseNumber() {
        std::string number;
        while (std::isdigit(peek()) || peek() == '.') {
            number += consume();
        }
        return number;
    }

    std::string parseRoot() {
        consume();  // Consume 'r'
        if (peek() != 'o' && peek() != 'O' && peek() != 't') {
            // Invalid root format
            throw std::invalid_argument("Invalid root format");
        }

        // Handle 'root'
        std::string rootName;
        while (peek() == 'o' || peek() == 'O' || peek() == 't' || peek() == '(') {
            rootName += consume();
        }

        if (peek() != '(') {
            // Invalid root format
            throw std::invalid_argument("Invalid root format");
        }
        consume();  // Consume '('

        std::string degreeStr;
        while (std::isdigit(peek())) {
            degreeStr += consume();
        }
        int degree = std::stoi(degreeStr);

        if (peek() != ')') {
            // Invalid root format
            throw std::invalid_argument("Invalid root format");
        }
        consume();  // Consume ')'

        std::string base = parseExpression();

        return "(" + base + ")^(1/" + std::to_string(degree) + ")";
    }

    std::string parseFactor() {
        std::string result;

        while (std::isalnum(peek()) || peek() == '^' || peek() == '(' || peek() == ')' || peek() == '[' || peek() == ']') {
            if (peek() == 'r' && expression.substr(index, 5) == "root(") {
                result += parseRoot();
            } else if (peek() == 's' && expression.substr(index, 4) == "sqrt") {
                consume();  // Consume 's'
                consume();  // Consume 'q'
                consume();  // Consume 'r'
                consume();  // Consume 't'
                consume();  // Consume '('
                result += "(" + parseExpression() + ")^(1/2)";
                if (peek() == ')') {
                    consume(); // Consume ')'
                } else {
                    // Invalid sqrt format
                    throw std::invalid_argument("Invalid sqrt format");
                }
            } else if (peek() == '^') {
                consume();  // Consume '^'
                std::string exponent = parseNumber();
                result += "^(" + exponent + ")";
            } else {
                result += consume();
            }
        }

        return result;
    }

    std::string parseTerm() {
        std::string left = parseFactor();
        while (peek() == '*' || peek() == '/') {
            char op = consume();
            std::string right = parseFactor();
            left = left + op + right;
        }
        return left;
    }

    std::string parseExpression() {
        std::string left = parseTerm();
        while (peek() == '+' || peek() == '-') {
            char op = consume();
            std::string right = parseTerm();
            left = left + op + right;
        }
        return left;
    }
};

int main() {
    std::string input;
    std::cout << "Podaj wyrazenie matematyczne: ";
    std::getline(std::cin, input);

    ExpressionParser parser;
    try {
        std::string result = parser.parse(input);
        std::cout << "Przeksztacone wyrazenie: " << result << std::endl;
    } catch (const std::invalid_argument& e) {
        std::cerr << "B³¹d: " << e.what() << std::endl;
    }

    return 0;
}

 

---

Wydaje mi się że analogicznie, tylko musisz właśnie dwukrotnie wywołać parseExpression z parseRoot - raz po '(', raz po '['.

BTW jak już masz taką klasę napisaną, to dodaj jedną metodę obok peek i consume, żeby zamiast

        // Handle 'root'
        std::string rootName;
        while (peek() == 'o' || peek() == 'O' || peek() == 't' || peek() == '(') {
            rootName += consume();
        }

było po prostu

consumeExpect('o');
consumeExpect('o');
consumeExpect('t');
consumeExpect('(');

lub bezpośrednio

consumeExpect("oot(");

co zwraca boola czy się udało, albo od razu rzuca wyjątkiem. Będzie tak trochę prostszy kod :)

(choć można też to napisać bez tego wszystkiego)

---

dzięki za pomysł :)

---

Mam taki kod i on działa prawidłowo, zagnieżdżone pierwiastki także działają. 

Teraz chce tylko zrobić tak żeby ten algorytm obsługiwał takie coś sqrt(3-2(2+3)), chce żeby  można było wprowadzać nawiasy wewnątrz pierwiastka. Bo na razie pisze mi że invalid format sqrt. 

#include <iostream>
#include <string>
#include <cmath>

class ExpressionParser {
public:
    std::string parse(const std::string& expression) {
        this->expression = expression;
        this->index = 0;
        return parseExpression();
    }

private:
    std::string expression;
    size_t index;

    char peek() {
        if (index < expression.size()) {
            return expression[index];
        }
        return '\0';
    }

    char consume() {
        if (index < expression.size()) {
            return expression[index++];
        }
        return '\0';
    }

    std::string parseNumber() {
        std::string number;
        while (std::isdigit(peek()) || peek() == '.') {
            number += consume();
        }
        return number;
    }

    std::string parseRoot() {
        consume(); // Consume 'r'
        consume(); // Consume 'o'
        consume(); // Consume 'o'
        consume(); // Consume 't'

        if (peek() == '(') {
            consume(); // Consume '('
            std::string degreeStr;
            while (std::isdigit(peek())) {
                degreeStr += consume();
            }
            int degree = std::stoi(degreeStr);

            if (peek() == ')') {
                consume(); // Consume ')'

                if (peek() == '[') {
                    consume(); // Consume '['
                    std::string innerExpr = parseExpression();

                    if (peek() == ']') {
                        consume(); // Consume ']'
                        return "(" + innerExpr + ")^(1/" + std::to_string(degree) + ")";
                    } else {
                        throw std::invalid_argument("Invalid root format");
                    }
                } else {
                    throw std::invalid_argument("Invalid root format");
                }
            } else {
                throw std::invalid_argument("Invalid root format");
            }
        } else {
            throw std::invalid_argument("Invalid root format");
        }
    }

    std::string parseFactor() {
    std::string result;

    if (peek() == 's') {
        if (expression.substr(index, 4) == "sqrt") {
            index += 4; // Consume 'sqrt'
            if (peek() == '(') {
                consume(); // Consume '('
                std::string innerExpr = parseExpression();
                if (peek() == ')') {
                    consume(); // Consume ')'
                    result += "sqrt(" + innerExpr + ")";
                } else {
                    throw std::invalid_argument("Invalid sqrt format");
                }
            }
        }
    } else if (peek() == 'c') {
        if (expression.substr(index, 4) == "cbrt") {
            index += 4; // Consume 'cbrt'
            if (peek() == '(') {
                consume(); // Consume '('
                std::string innerExpr = parseExpression();
                if (peek() == ')') {
                    consume(); // Consume ')'
                    result += "cbrt(" + innerExpr + ")";
                } else {
                    throw std::invalid_argument("Invalid cbrt format");
                }
            }
        }
    } else if (peek() == 'r') {
        if (expression.substr(index, 4) == "root") {
            result += parseRoot();
        }
    } else if (peek() == '(') {
        consume(); // Consume '('
        result += "(" + parseExpression() + ")";
        if (peek() == ')') {
            consume(); // Consume ')'
        } else {
            throw std::invalid_argument("Unbalanced parentheses");
        }
    } else if (peek() == '^') {
        consume(); // Consume '^'
        std::string exponent = parseNumber();
        result += "^(" + exponent + ")";
    } else {
        result += parseNumber();
    }

    return result;
}

std::string parseTerm() {
    std::string left = parseFactor();
    while (peek() == '*' || peek() == '/') {
        char op = consume();
        std::string right = parseFactor();
        left = left + op + right;
    }
    return left;
}


    std::string parseExpression() {
        std::string left = parseTerm();
        while (peek() == '+' || peek() == '-') {
            char op = consume();
            std::string right = parseTerm();
            left = left + op + right;
        }
        return left;
    }
};

int main() {
    std::string input;
    std::cout << "Podaj wyrazenie matematyczne: ";
    std::getline(std::cin, input);

    ExpressionParser parser;
    try {
        std::string result = parser.parse(input);
        std::cout << "Przeksztacone wyrazenie: " << result << std::endl;
    } catch (const std::invalid_argument& e) {
        std::cerr << "Błąd: " << e.what() << std::endl;
    }

    return 0;
}