Infix and Postfix Expressions

Mathematical expressions typically follow enfix notation, where operators appear between operands. Alternatively, postfix notation places operators after operands. While infix notation aligns with human cognition, postfix notation offers computational advantages by eliminating parentheses and preserving operator precedence.

Calculator Core Algorithm

The expression evaluation process involves three key steps:

1. Tokenize infix expressions into numbers and operators
2. Convert infix expressions to postfix notation
3. Evaluate postfix expressions to produce results

Tokenization Algorithm

The tokenization process analyzes each character sequentially using a state-based approach:

• Maintain a current token buffer
• Accumulate digits and decimal points into the buffer
• When encountering symbols:
  • Finalize and store completed number tokens
  • Handle operator/sign ambiguity using contextual analysis
• Special cases for sign identification:
  • Expression-starting signs
  • Signs following parentheses
  • Signs after operators

ExpressionTokenizer.h

#ifndef EXPRESSIONTOKENIZER_H
#define EXPRESSIONTOKENIZER_H

#include <QQueue>
#include <QString>

class ExpressionTokenizer {
public:
    ExpressionTokenizer();
    QQueue<QString> processExpression(const QString& input);
    
private:
    bool isNumeric(QChar c);
    bool isSymbol(QChar c);
    bool isSign(QChar c);
    bool isOperator(QString s);
    QQueue<QString> tokenize(const QString& expr);
};
#endif

ExpressionTokenizer.cpp

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

ExpressionTokenizer::ExpressionTokenizer() {
    auto tokens = tokenize("+9--8+(+4)-5");
    for (const auto& token : tokens) {
        qDebug() << token;
    }
}

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

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

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

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

QQueue<QString> ExpressionTokenizer::tokenize(const QString& expr) {
    QQueue<QString> tokens;
    QString current = "";
    QString previous = "";

    for (int i = 0; i < expr.length(); ++i) {
        if (isNumeric(expr[i])) {
            current += expr[i];
            previous = expr[i];
        }
        else if (isSymbol(expr[i])) {
            if (!current.isEmpty()) {
                tokens.enqueue(current);
                current.clear();
            }

            if (isSign(expr[i]) && 
                (previous.isEmpty() || previous == "(" || isOperator(previous))) {
                current += expr[i];
            }
            else {
                tokens.enqueue(QString(expr[i]));
            }
            previous = expr[i];
        }
    }

    if (!current.isEmpty()) {
        tokens.enqueue(current);
    }
    return tokens;
}

Main Implementation

#include <QtCore/QCoreApplication>
#include "ExpressionTokenizer.h"

int main(int argc, char* argv[]) {
    ExpressionTokenizer parser;
    return 0;
}

Key Concepts

• QString uses 2-byte QChar elements
• Qt provides essential data structure implementations
• Expression evaluation requires:
  1. Token separation
  2. Infix-to-postfix conversion
  3. Postfix evaluation