#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <cctype>
#include <map>
#include <stdexcept>
#include <cmath>

// 演算子の優先順位と結合性を定義
struct OpInfo {
    int precedence;
    bool right_associative;
};

const std::map<char, OpInfo> OP_MAP = {
    {'+', {1, false}},
    {'-', {1, false}},
    {'*', {2, false}},
    {'/', {2, false}},
    {'^', {3, true}} // 累乗にも対応
};

// トークンの種類
enum TokenType { NUMBER, OPERATOR, LPAREN, RPAREN };

struct Token {
    TokenType type;
    std::string value;
};

// 文字列をトークンに分解（字句解析）
std::vector<Token> tokenize(const std::string& expr) {
    std::vector<Token> tokens;
    size_t i = 0;
    while (i < expr.length()) {
        if (std::isspace(expr[i])) {
            i++;
            continue;
        }
        if (std::isdigit(expr[i]) || expr[i] == '.') {
            std::string num;
            while (i < expr.length() && (std::isdigit(expr[i]) || expr[i] == '.')) {
                num += expr[i++];
            }
            tokens.push_back({NUMBER, num});
        } else if (OP_MAP.count(expr[i])) {
            // 負の数の処理（式の先頭、または別の演算子・左括弧の直後のマイナス）
            if (expr[i] == '-' && (tokens.empty() || tokens.back().type == OPERATOR || tokens.back().type == LPAREN)) {
                tokens.push_back({NUMBER, "-1"});
                tokens.push_back({OPERATOR, "*"});
                i++;
            } else {
                tokens.push_back({OPERATOR, std::string(1, expr[i++])});
            }
        } else if (expr[i] == '(') {
            tokens.push_back({LPAREN, "("});
            i++;
        } else if (expr[i] == ')') {
            tokens.push_back({RPAREN, ")"});
            i++;
        } else {
            throw std::runtime_error("不正な文字が含まれています: " + std::string(1, expr[i]));
        }
    }
    return tokens;
}

// 2つの数値と演算子から計算を行う
double applyOp(double a, double b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        case '/': 
            if (b == 0) throw std::runtime_error("エラー: ゼロ除算が発生しました");
            return a / b;
        case '^': return std::pow(a, b);
        default: throw std::runtime_error("未知の演算子です");
    }
}

// 操車場アルゴリズムによる数式の評価
double evaluate(const std::string& expr) {
    auto tokens = tokenize(expr);
    std::stack<double> values;
    std::stack<char> ops;

    for (const auto& token : tokens) {
        if (token.type == NUMBER) {
            values.push(std::stod(token.value));
        } else if (token.type == LPAREN) {
            ops.push('(');
        } else if (token.type == RPAREN) {
            while (!ops.empty() && ops.top() != '(') {
                if (values.size() < 2) throw std::runtime_error("式が不正です");
                double val2 = values.top(); values.pop();
                double val1 = values.top(); values.pop();
                values.push(applyOp(val1, val2, ops.top()));
                ops.pop();
            }
            if (ops.empty()) throw std::runtime_error("括弧の対応が取れていません");
            ops.pop(); // '(' を除去
        } else if (token.type == OPERATOR) {
            char op = token.value[0];
            while (!ops.empty() && ops.top() != '(') {
                char topOp = ops.top();
                if ((!OP_MAP.at(op).right_associative && OP_MAP.at(op).precedence <= OP_MAP.at(topOp).precedence) ||
                    (OP_MAP.at(op).right_associative && OP_MAP.at(op).precedence < OP_MAP.at(topOp).precedence)) {
                    if (values.size() < 2) throw std::runtime_error("式が不正です");
                    double val2 = values.top(); values.pop();
                    double val1 = values.top(); values.pop();
                    values.push(applyOp(val1, val2, topOp));
                    ops.pop();
                } else {
                    break;
                }
            }
            ops.push(op);
        }
    }

    while (!ops.empty()) {
        if (ops.top() == '(') throw std::runtime_error("括弧の対応が取れていません");
        if (values.size() < 2) throw std::runtime_error("式が不正です");
        double val2 = values.top(); values.pop();
        double val1 = values.top(); values.pop();
        values.push(applyOp(val1, val2, ops.top()));
        ops.pop();
    }

    if (values.size() != 1) throw std::runtime_error("式が不正です");
    return values.top();
}

int main() {
    std::cout << "--- 数式計算プログラム (終了するには 'exit' と入力) ---" << std::endl;
    std::string input;
    while (true) {
        std::cout << "数式を入力: ";
        std::getline(std::cin, input);
        if (input == "exit") break;
        if (input.empty()) continue;

        try {
            double result = evaluate(input);
            std::cout << "結果: " << result << std::endl;
        } catch (const std::exception& e) {
            std::cerr << e.what() << std::endl;
        }
    }
    return 0;
}