Expression Evaluation Implementation

The following solution demonstrates arithmetic expression evaluation in Qt with support for negative numbers. The implementation converts infix expressions to postfix notation before evaluation.

Expression Repair Mechanism

void repairExpression(QString &expression) {
    bool needsRepair = false;
    int lastOpPos = -1;
    QString result;
    
    for(int i = 0; i < expression.length(); ++i) {
        QChar current = expression[i];
        
        if(current.isOperator()) {
            if(needsRepair) {
                result.append(')');
                needsRepair = false;
            }

            if(current == '-' && (i == 0 || lastOpPos == i - 1)) {
                result.append('(0');
                needsRepair = true;
            }
            lastOpPos = i;
        }
        result.append(current);
    }
    expression = result;
}

Infix to Postfix Conversion

QString convertToPostfix(const QString &infix) {
    QString output;
    QStack<QChar> operatorStack;
    
    QMap<QChar, int> precedence = {
        {'(', 0}, {')', 0},
        {'+', 1}, {'-', 1},
        {'*', 2}, {'/', 2}
    };

    for(int i = 0; i < infix.length(); ++i) {
        QChar token = infix[i];
        
        if(token == ' ') continue;
        
        if(token == '-' && (i == 0 || precedence.contains(infix[i-1]))) {
            output.append('0');
        }

        if(precedence.contains(token)) {
            if(token == ')') {
                while(!operatorStack.isEmpty() && operatorStack.top() != '(') {
                    output.append(' ');
                    output.append(operatorStack.pop());
                }
                operatorStack.pop();
            }
            else if(operatorStack.isEmpty() || token == '(' || 
                   precedence[token] > precedence[operatorStack.top()]) {
                operatorStack.push(token);
            }
            else {
                while(!operatorStack.isEmpty() && 
                      precedence[token] <= precedence[operatorStack.top()]) {
                    output.append(' ');
                    output.append(operatorStack.pop());
                }
                operatorStack.push(token);
            }
            output.append(' ');
        }
        else {
            output.append(token);
        }
    }

    while(!operatorStack.isEmpty()) {
        output.append(' ');
        output.append(operatorStack.pop());
    }
    
    return output;
}

Postfix Evaluation

double evaluatePostfix(const QStringList &tokens) {
    QStack<double> valueStack;
    
    for(const QString &token : tokens) {
        if(token.length() == 1 && "+-*/".contains(token[0])) {
            double right = valueStack.pop();
            double left = valueStack.pop();
            
            switch(token[0].toLatin1()) {
                case '+': valueStack.push(left + right); break;
                case '-': valueStack.push(left - right); break;
                case '*': valueStack.push(left * right); break;
                case '/': valueStack.push(left / right); break;
            }
        }
        else {
            valueStack.push(token.toDouble());
        }
    }
    
    return valueStack.pop();
}

Usage Example

void testExpressions() {
    QString expr1 = "1 + 2.3 * (23 + 3)";
    QString expr2 = "1*(-3)+2*(3+3)";
    QString expr3 = "2*-3+-2.1*(3+3)";
    
    repairExpression(expr1);
    repairExpression(expr2);
    repairExpression(expr3);
    
    QString postfix1 = convertToPostfix(expr1);
    QString postfix2 = convertToPostfix(expr2);
    QString postfix3 = convertToPostfix(expr3);
    
    qDebug() << evaluatePostfix(postfix1.split(' ', QString::SkipEmptyParts));
    qDebug() << evaluatePostfix(postfix2.split(' ', QString::SkipEmptyParts));
    qDebug() << evaluatePostfix(postfix3.split(' ', QString::SkipEmptyParts));
}