中置記法から後置記法への変換

数式をプログラムで評価する際、中置記法（infix notation）を後置記法（postfix notation、逆ポーランド記法）に変換することが一般的である。この変換はスタックを用いたアルゴリズムにより実現され、以下の特徴を持つ：

• 入力式の括弧が正しく対応している必要がある。
• 演算子の優先順位に基づいて変換が行われる。
• 出力される後置記法には括弧が含まれない。
• 変換後の式は左から右へ順次評価することで結果が得られる。

変換アルゴリズムの手順

1. 数値の場合：即座に出力キューに追加する。
2. 演算子の場合：
   • スタックのトップにある演算子と優先順位を比較する。
   • 現在の演算子の優先順位がスタックトップ以下であれば、スタックからポップして出力キューに追加し、再度比較を行う。
   • 優先順位が高い場合は、スタックにプッシュする。
3. 左括弧 '(' の場合：スタックにプッシュする。
4. 右括弧 ')' の場合：
   • スタックトップが左括弧になるまで、スタックからポップして出力キューに追加する。
   • 左括弧は出力せず、スタックから破棄する。

括弧の整合性検証

有効な数式では、括弧は必ずペアで出現し、左括弧が右括弧より先に現れる必要がある。この条件を満たすかどうかをスタックを使って検証できる：

• 左括弧をスタックにプッシュする。
• 右括弧に遭遇したとき、スタックが空でなく、トップが左括弧であればポップする。
• そうでなければ不整合と判断し、エラーとする。
• 処理終了時にスタックが空でなければ、括弧が閉じられていないことを意味し、エラーとなる。

コード例：式のトークン分割と変換

以下は、Qtフレームワークを用いた式の解析および中置→後置変換の実装例である。

#ifndef QCALCULATORDEC_H
#define QCALCULATORDEC_H

#include <QQueue>
#include <QString>
#include <QStack>

class QCalculatorDec {
protected:
    bool isDigitOrDot(QChar c);
    bool isSymbol(QChar c);
    bool isSign(QChar c);
    bool isOperator(const QString& s);
    QQueue<QString> tokenize(const QString& expr);

    bool isNumber(const QString& s);
    bool isLeftParen(const QString& s);
    bool isRightParen(const QString& s);
    int getPriority(const QString& op);
    bool validateBrackets(QQueue<QString>& tokens);
    bool infixToPostfix(QQueue<QString>& input, QQueue<QString>& output);

public:
    QCalculatorDec();
    ~QCalculatorDec();
};

#endif // QCALCULATORDEC_H

#include "QCalculatorDec.h"
#include <QDebug>

QCalculatorDec::QCalculatorDec() {
    QQueue<QString> tokens = tokenize("(8+3)-5");
    for (const auto& token : tokens) {
        qDebug() << token;
    }

    QQueue<QString> postfix;
    if (infixToPostfix(tokens, postfix)) {
        qDebug() << "\nPostfix:";
        for (const auto& token : postfix) {
            qDebug() << token;
        }
    }
}

bool QCalculatorDec::isDigitOrDot(QChar c) {
    return (c >= '0' && c <= '9') || c == '.';
}

bool QCalculatorDec::isSymbol(QChar c) {
    return isOperator(QString(c)) || c == '(' || c == ')';
}

bool QCalculatorDec::isSign(QChar c) {
    return c == '+' || c == '-';
}

bool QCalculatorDec::isOperator(const QString& s) {
    return s == "+" || s == "-" || s == "*" || s == "/";
}

QQueue<QString> QCalculatorDec::tokenize(const QString& expr) {
    QQueue<QString> result;
    QString numberBuffer;
    QString prevToken;

    for (int i = 0; i < expr.length(); ++i) {
        QChar ch = expr[i];
        if (isDigitOrDot(ch)) {
            numberBuffer += ch;
            prevToken = QString(ch);
        } else if (isSymbol(ch)) {
            if (!numberBuffer.isEmpty()) {
                result.enqueue(numberBuffer);
                numberBuffer.clear();
            }

            QString current = QString(ch);
            if (isSign(ch) && (prevToken.isEmpty() || prevToken == "(" || isOperator(prevToken))) {
                numberBuffer = current;
            } else {
                result.enqueue(current);
            }
            prevToken = current;
        }
    }

    if (!numberBuffer.isEmpty()) {
        result.enqueue(numberBuffer);
    }
    return result;
}

bool QCalculatorDec::isNumber(const QString& s) {
    bool ok;
    s.toDouble(&ok);
    return ok;
}

bool QCalculatorDec::isLeftParen(const QString& s) {
    return s == "(";
}

bool QCalculatorDec::isRightParen(const QString& s) {
    return s == ")";
}

int QCalculatorDec::getPriority(const QString& op) {
    if (op == "+" || op == "-") return 1;
    if (op == "*" || op == "/") return 2;
    return 0;
}

bool QCalculatorDec::validateBrackets(QQueue<QString>& tokens) {
    QStack<QString> stack;
    for (const QString& token : tokens) {
        if (isLeftParen(token)) {
            stack.push(token);
        } else if (isRightParen(token)) {
            if (stack.isEmpty() || !isLeftParen(stack.top())) {
                return false;
            }
            stack.pop();
        }
    }
    return stack.isEmpty();
}

bool QCalculatorDec::infixToPostfix(QQueue<QString>& input, QQueue<QString>& output) {
    if (!validateBrackets(input)) {
        return false;
    }

    QStack<QString> opStack;
    output.clear();

    while (!input.isEmpty()) {
        QString token = input.dequeue();

        if (isNumber(token)) {
            output.enqueue(token);
        } else if (isOperator(token)) {
            while (!opStack.isEmpty() && getPriority(token) <= getPriority(opStack.top())) {
                output.enqueue(opStack.pop());
            }
            opStack.push(token);
        } else if (isLeftParen(token)) {
            opStack.push(token);
        } else if (isRightParen(token)) {
            while (!opStack.isEmpty() && !isLeftParen(opStack.top())) {
                output.enqueue(opStack.pop());
            }
            if (!opStack.isEmpty()) {
                opStack.pop(); // 左括弧を破棄
            }
        } else {
            return false; // 不明なトークン
        }
    }

    while (!opStack.isEmpty()) {
        output.enqueue(opStack.pop());
    }

    return true;
}

QCalculatorDec::~QCalculatorDec() {}

この実装では、まず入力文字列を数値・演算子・括弧などのトークンに分割し、その後、括弧の整合性を検証した上で中置記法から後置記法へ変換する。変換過程で構文エラー（例：括弧の不整合、無効な演算子など）が検出された場合、処理は失敗として扱われる。