中缀表达式转为后缀表达式用Qt实现代码,要求后缀表达式的数字以#结尾并且能正确在Qt上执行
时间: 2024-02-11 14:09:34 浏览: 31
下面是一个用Qt实现中缀表达式转为后缀表达式的代码示例:
```cpp
#include <QtDebug>
#include <QStack>
#include <QRegularExpression>
#include <QStringList>
QString infixToPostfix(const QString& infix)
{
QStringList tokens = infix.split(QRegularExpression("\\s+"), QString::SkipEmptyParts);
QStack<QString> stack;
QString postfix;
for (const QString& token : tokens) {
if (token == "(") {
stack.push(token);
} else if (token == ")") {
while (!stack.isEmpty() && stack.top() != "(") {
postfix += stack.pop() + " ";
}
if (stack.isEmpty()) {
qWarning() << "Mismatched parentheses";
return QString();
}
stack.pop(); // pop "("
} else if (token == "+" || token == "-" || token == "*" || token == "/") {
int precedence = 0;
if (token == "+" || token == "-") {
precedence = 1;
} else if (token == "*" || token == "/") {
precedence = 2;
}
while (!stack.isEmpty() && stack.top() != "(" && (precedence < getPrecedence(stack.top()))) {
postfix += stack.pop() + " ";
}
stack.push(token);
} else {
postfix += token + " ";
}
}
while (!stack.isEmpty()) {
if (stack.top() == "(") {
qWarning() << "Mismatched parentheses";
return QString();
}
postfix += stack.pop() + " ";
}
postfix += "#"; // add end marker
return postfix;
}
int evaluatePostfix(const QString& postfix)
{
QStringList tokens = postfix.split(QRegularExpression("\\s+"), QString::SkipEmptyParts);
QStack<int> stack;
for (const QString& token : tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
if (stack.size() < 2) {
qWarning() << "Invalid postfix expression";
return 0;
}
int b = stack.pop();
int a = stack.pop();
int result = 0;
if (token == "+") {
result = a + b;
} else if (token == "-") {
result = a - b;
} else if (token == "*") {
result = a * b;
} else if (token == "/") {
if (b == 0) {
qWarning() << "Division by zero";
return 0;
}
result = a / b;
}
stack.push(result);
} else {
bool ok = false;
int value = token.toInt(&ok);
if (!ok) {
qWarning() << "Invalid token:" << token;
return 0;
}
stack.push(value);
}
}
if (stack.size() != 1) {
qWarning() << "Invalid postfix expression";
return 0;
}
return stack.pop();
}
int getPrecedence(const QString& op)
{
if (op == "+" || op == "-") {
return 1;
} else if (op == "*" || op == "/") {
return 2;
} else {
return 0;
}
}
int main()
{
QString infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3";
QString postfix = infixToPostfix(infix);
qDebug() << "Postfix:" << postfix;
int result = evaluatePostfix(postfix);
qDebug() << "Result:" << result;
return 0;
}
```
这个示例代码中,`infixToPostfix()`函数将中缀表达式转换为后缀表达式,并在后缀表达式的末尾添加了一个#作为结束符。`evaluatePostfix()`函数计算后缀表达式的值。`getPrecedence()`函数返回运算符的优先级。在主函数中,我们将一个字符串中缀表达式传递给`infixToPostfix()`函数,并输出转换得到的后缀表达式和计算结果。
需要注意的是,这个示例代码中只处理了整数和四则运算,对于更复杂的表达式可能需要进行额外的处理。同时,这个代码示例还没有进行错误处理,例如不匹配的括号、无效的表达式等情况。在实际应用中需要根据具体需求进行相应的处理。