字符串四则运算表达式求值

四则表达式求值示例：

示例中的运算式子为10+20-30+4*(20-10+20*10-100)，运算结果为440

1. 后缀表达式

对于四则运算表达式，如 10+20-3*(10-5)+8 ，我们如何用程序实现这个运算表达式求值呢？可以使用 一种不需要括号的后缀表达法，我们也称为逆波兰（RPN）表示，如上面的例子
10+20-3*(10-5)+8，使用后缀表示法就变成了这样
10 20 + 3 10 5 - * - 8 +
我们把这样的式子称为后缀表达式，叫后缀的原因为 所有的符号都在要运算数字的后面，那么我们如何使用后缀表达式计算结果呢？

以上面的后缀表达式为例，运算规则是这样的 从前往后，遇到数字则入栈，遇到符号则出栈做运算，将运算结果再入栈。 这里使用栈的特性，先进先出（FILO）。

所以根据上面的规则，计算该后缀表达式的步骤如下：

1. 10 和 20 入栈，此时栈中元素为（10，20）
2. 运算符号 “+” 号， 栈中元素出栈（10 和 20）做 “+” 操作后，结果（30），入栈；此时栈中元素为30。
3. 数字 3、10、5 依次入栈，此时栈中元素为（30，3，10，5）
4. 运算符号 “-” 号，栈中元素出栈（10 和 5），注意此时栈顶元素为5，出栈后栈顶元素为10，操作时顺序为 10 - 5， 结果为5，入栈；此时栈中元素为（30，3，5）
5. 运算符号 “*”，栈中元素出栈（3 和 5）做 “*” 操作后，结果（15），入栈；此时栈中元素为（30，15）
6. 运算符号 “-” ，元素出栈（30和15）做 “-” 操作后，结果为（15），入栈；此时栈中元素为（15）
7. 数字 8 入栈，此时栈中元素为 （15， 8）
8. 运算符号 “+” ，元素出栈 （15和8）做 “+” 操作后，结果为（23）入栈；此时栈中元素为（23），至此运算结束，运算结果为23

2. 后缀表达式的推倒

我们把平时运算中用的四则表达式称为 中缀表达式，因为运算符号都在中间，那么我们如何将中缀表达式转化为后缀表达式呢？
规则如下：

从左到右遍历中缀表达式中每一个数字和符号，若是数字则输出，称为中缀表达式中的一部分；若是符号则判读其与栈顶符号的优先级，是右括号或者优先级不高于栈顶符号（乘除高于加减）则栈顶元素依次出栈并输出，直到栈为空或者栈顶符号优先级低于该符号为止，并将当前符号进栈。一直到最终输出后缀表达式为指

我们同样依据上面的例子来进行说明，将中缀表达式10+20-3*(10-5)+8，转化为后缀表达式10 20 + 3 10 5 - * - 8 +

1. 输出10，此时后缀表达式输出为 (10)
2. 符号 “+” 入栈，此时符号栈中元素为（+）
3. 输出20，此时后缀表达式输出为 (10，20)
4. 符号“-” ，栈顶元素比对，栈顶元素“+” 不高于“-”号，出栈并输出，此时后缀表达式输出为 (10，20，+)，符号入栈此时符号栈中元素为（-）
5. 输出3，此时后缀表达式输出为 (10，20，+，3)
6. 符号“*” 入栈，此时符号栈中元素为（-，*）
7. 符号“（” 入栈，此时符号栈中元素为（-，*，"(" ）
8. 输出10，此时后缀表达式输出为 (10，20，+，3，10)
9. 符号“-” 入栈，此时符号栈中元素为（-，*，"(" ，-）
   10.数字5输出， 此时后缀表达式输出为 (10，20，+，3，10，5)
10. 符号“)”，符号出栈直到匹配小括号“(”为止，此时符号栈中元素为（-，*），此时后缀表达式输出为 (10，20，+，3，10，5， -)
11. 符号“+”，栈顶元素“*”优先级不低于“+”号，出栈输出；此时栈顶元素“-”号也不低于符号“+”，出栈输出；此时符号栈为空，当前符号入栈，此时符号栈中元素为（+），此时后缀表达式输出为 (10，20，+，3，10，5， -，*, -)
12. 输出数字8，此时后缀表达式输出为 (10，20，+，3，10，5， -，*, -， 8)
13. 符号栈中元素全部出栈，即最终后缀表达式为 10 20 + 3 10 5 - * - 8 +

下面是关于输入任意字符串后计算表达式的值的代码：

int calcResult(QString string)
{
    // QString转Char*
    QByteArray byteArray = string.toLocal8Bit();
    char* pString = byteArray.data();

    QString tempString;
    QStringList tempStringList;		// 用于存放后缀结果
    QVector<char> operStack;

    for (int i = 0; i < string.length(); ++i)
    {
        if (pString[i] >= '0' && pString[i] <= '9')
            tempString.append(QChar(pString[i]));
        else
        {
            // 如果为符号，则将数字加入到结果列表中
            if (!tempString.isEmpty())
            {
                tempStringList.append(tempString);
                tempString.clear();
            }
            
            char cValue = pString[i];

            // "("直接入栈
            if (cValue == '(')
                operStack.push_back(cValue);
            // 栈顶元素优先级不大于该符号则出栈，即若为 * 和 / 则出栈
            else if (cValue == '*' || cValue == '/')
            {
                while (!operStack.isEmpty())
                {
                    int size = operStack.size();
                    char cOper = operStack[size - 1];
                    if (cOper == '*' || cOper == '/')
                        tempStringList.push_back(QChar(cOper));
                    else
                        break;
                    operStack.pop_back();
                }
                operStack.push_back(cValue);
            }
            // 若为)则匹配到(为止的所有符号出栈
            else if (cValue == ')')
            {
                // 出栈到匹配(为止
                char cTopStack = *(operStack.end() - 1);
                while (cTopStack != '(')
                {
                    tempStringList.push_back(QChar(cTopStack));
                    operStack.pop_back();

                    cTopStack = *(operStack.end() - 1);
                }
                // 使(出栈
                operStack.pop_back();
            }
            // 栈顶元素优先级不大于该符号则出栈，即若为 + 、 - 、* 、/ 则出栈
            else if (cValue == '+' || cValue == '-')
            {
                while (!operStack.isEmpty())
                {
                    char cOper = *(operStack.end() - 1);
                    if (cOper == '+' || cOper == '-' || cOper == '*' || cOper == '/')
                    {
                        tempStringList.push_back(QChar(cOper));
                        operStack.pop_back();
                    }
                    else
                        break;
                }
                // 该符号入栈
                operStack.push_back(cValue);
            }
        }
    }

    if (!tempString.isEmpty())
        tempStringList.append(tempString);
    while (!operStack.isEmpty())
    {
        tempStringList.append(QChar(*(operStack.end() - 1)));
        operStack.pop_back();
    }

    // 根据后缀表达式计算结果
    QVector<int> numberStack;	// 数字栈
    for (auto iter = tempStringList.begin(); iter != tempStringList.end(); ++iter)
    {
        QString tempValue = *iter;

        bool isNumber = false;
        int number = tempValue.toInt(&isNumber);
        if (isNumber)
            numberStack.push_back(number);
        else
        {
            // 取出栈顶的两个数
            int count = numberStack.count();
            int number1 = numberStack[count - 2];
            int number2 = numberStack[count - 1];
            numberStack.pop_back();
            numberStack.pop_back();

            int result = 0;	// 计算结果
            if (tempValue == "+")
                result = number1 + number2;
            else if (tempValue == "-")
                result = number1 - number2;
            else if (tempValue == "*")
                result = number1 * number2;
            else if (tempValue == "/")
                result = number1 / number2;

            // 将结果入栈
            numberStack.push_back(result);
        }
    }

    return numberStack[0];
}

完整代码如下：
头文件：

#pragma once

#include <QtWidgets/QWidget>
#include <QLabel>
#include <QLineEdit>
#include <QPushButton>
#include <QVector>

class FourOperWidget : public QWidget
{
    Q_OBJECT

public:
    FourOperWidget();
    ~FourOperWidget();

private:
    QLabel *m_ResultTag = nullptr;
    QLineEdit *m_CalcLineEdit = nullptr;
    QPushButton *m_PushButton = nullptr;

protected:
    bool eventFilter(QObject *watched, QEvent *event) override;

private slots:
    void onCalcButtonClicked(void);

private:
    int calcResult(QString string);
};

.cpp文件

#include "FouOperWidget.h"
#include <iostream>
#include <QVBoxLayout>
#include <QEvent>
#include <QKeyEvent>

FourOperWidget::FourOperWidget()
{

    m_ResultTag = new QLabel;
    m_ResultTag->setStyleSheet("font-size: 30px; color: rgb(255, 0, 0);");
    m_ResultTag->setMinimumHeight(50);
    m_CalcLineEdit = new QLineEdit;
    m_CalcLineEdit->installEventFilter(this);

    QString str = QString::fromLocal8Bit("计算");
    m_PushButton = new QPushButton(str);
    QObject::connect(m_PushButton, SIGNAL(clicked()), this, SLOT(onCalcButtonClicked()));

    QVBoxLayout *layout = new QVBoxLayout(this);

    QHBoxLayout *topLayout = new QHBoxLayout;
    layout->addLayout(topLayout);
    topLayout->addWidget(m_CalcLineEdit);
    topLayout->addWidget(m_PushButton);

    QLabel *resultTag = new QLabel(QString::fromLocal8Bit("计算结果为："));
    layout->addWidget(resultTag);
    layout->addWidget(m_ResultTag);

    layout->addStretch();
}

FourOperWidget::~FourOperWidget()
{

}

void FourOperWidget::onCalcButtonClicked(void)
{
    QString str = m_CalcLineEdit->text();
    if (str.isEmpty())
        return;

    int result = calcResult(str);
    m_ResultTag->setText(QString::number(result));
}

int FourOperWidget::calcResult(QString string)
{
    // QString转Char*
    QByteArray byteArray = string.toLocal8Bit();
    char* pString = byteArray.data();

    QString tempString;
    QStringList tempStringList;		// 用于存放后缀结果
    QVector<char> operStack;

    for (int i = 0; i < string.length(); ++i)
    {
        if (pString[i] >= '0' && pString[i] <= '9')
            tempString.append(QChar(pString[i]));
        else
        {
            // 如果为符号，则将数字加入到结果列表中
            if (!tempString.isEmpty())
            {
                tempStringList.append(tempString);
                tempString.clear();
            }
            
            char cValue = pString[i];

            // "("直接入栈
            if (cValue == '(')
                operStack.push_back(cValue);
            // 栈顶元素优先级不大于该符号则出栈，即若为 * 和 / 则出栈
            else if (cValue == '*' || cValue == '/')
            {
                while (!operStack.isEmpty())
                {
                    int size = operStack.size();
                    char cOper = operStack[size - 1];
                    if (cOper == '*' || cOper == '/')
                        tempStringList.push_back(QChar(cOper));
                    else
                        break;
                    operStack.pop_back();
                }
                operStack.push_back(cValue);
            }
            // 若为)则匹配到(为止的所有符号出栈
            else if (cValue == ')')
            {
                // 出栈到匹配(为止
                char cTopStack = *(operStack.end() - 1);
                while (cTopStack != '(')
                {
                    tempStringList.push_back(QChar(cTopStack));
                    operStack.pop_back();

                    cTopStack = *(operStack.end() - 1);
                }
                // 使(出栈
                operStack.pop_back();
            }
            // 栈顶元素优先级不大于该符号则出栈，即若为 + 、 - 、* 、/ 则出栈
            else if (cValue == '+' || cValue == '-')
            {
                while (!operStack.isEmpty())
                {
                    char cOper = *(operStack.end() - 1);
                    if (cOper == '+' || cOper == '-' || cOper == '*' || cOper == '/')
                    {
                        tempStringList.push_back(QChar(cOper));
                        operStack.pop_back();
                    }
                    else
                        break;
                }
                // 该符号入栈
                operStack.push_back(cValue);
            }
        }
    }

    if (!tempString.isEmpty())
        tempStringList.append(tempString);
    while (!operStack.isEmpty())
    {
        tempStringList.append(QChar(*(operStack.end() - 1)));
        operStack.pop_back();
    }

    // 根据后缀表达式计算结果
    QVector<int> numberStack;	// 数字栈
    for (auto iter = tempStringList.begin(); iter != tempStringList.end(); ++iter)
    {
        QString tempValue = *iter;

        bool isNumber = false;
        int number = tempValue.toInt(&isNumber);
        if (isNumber)
            numberStack.push_back(number);
        else
        {
            // 取出栈顶的两个数
            int count = numberStack.count();
            int number1 = numberStack[count - 2];
            int number2 = numberStack[count - 1];
            numberStack.pop_back();
            numberStack.pop_back();

            int result = 0;	// 计算结果
            if (tempValue == "+")
                result = number1 + number2;
            else if (tempValue == "-")
                result = number1 - number2;
            else if (tempValue == "*")
                result = number1 * number2;
            else if (tempValue == "/")
                result = number1 / number2;

            // 将结果入栈
            numberStack.push_back(result);
        }
    }

    return numberStack[0];
}

bool FourOperWidget::eventFilter(QObject *watched, QEvent *event)
{
    // 仅可以输入数字、+ - * / 和 ( ) 
    if (event->type() == QEvent::KeyPress)
    {
        QKeyEvent *keyEvent = static_cast<QKeyEvent*>(event);
        if (keyEvent == nullptr)
            return QWidget::eventFilter(watched, event);

        QString keyString = keyEvent->text();
        bool isNumber = false;
        keyString.toInt(&isNumber);
        if (isNumber)
            return false;

        if (keyString == "+" || keyString == "-" || \
            keyString == "*" || keyString == "/" || \
            keyString == "(" || keyString == ")")
            return false;

        if (keyEvent->key() == Qt::Key_Left || \
            keyEvent->key() == Qt::Key_Right || \
            keyEvent->key() == Qt::Key_Backspace)
            return false;

        return true;
    }

    return QWidget::eventFilter(watched, event);
}

这里我使用了 过滤器，使文本输入框只能输入数字、+、-、*、/、(、）、左右方向键和BackSpace键。关于过滤器的使用可参照
Qt中的事件（2）- 事件过滤器

不会飞的纸飞机

扫一扫二维码，了解我的更多动态。