Qt实现中缀表达式转后缀表达式,中缀表达式带括号
时间: 2023-07-07 08:08:22 浏览: 115
将中缀表达式转化为后缀表达式
可以使用栈来实现中缀表达式转后缀表达式,处理括号时需要特殊处理。
具体实现步骤如下:
1. 定义一个栈stack来存储运算符,定义一个列表res来存储后缀表达式;
2. 遍历中缀表达式,遇到数字直接添加到res中;
3. 遇到左括号,将其压入stack中;
4. 遇到右括号,将stack中的运算符弹出并加入到res中,直到遇到左括号,将左括号弹出并丢弃;
5. 遇到运算符,如果stack为空或者栈顶是左括号,则将该运算符压入stack中;否则,将stack中优先级大于或等于该运算符的运算符弹出并加入到res中,然后将该运算符压入stack中;
6. 遍历完中缀表达式后,将stack中剩余的运算符弹出并加入到res中;
7. res就是转换后的后缀表达式。
以下是一个示例代码:
```cpp
QStringList infixToPostfix(const QString& infix)
{
QStringList res;
QStack<QChar> stack;
for (int i = 0; i < infix.size(); i++)
{
QChar ch = infix[i];
if (ch.isDigit())
{
QString num;
while (i < infix.size() && infix[i].isDigit())
{
num += infix[i];
i++;
}
res << num;
i--;
}
else if (ch == '(')
{
stack.push(ch);
}
else if (ch == ')')
{
while (!stack.isEmpty() && stack.top() != '(')
{
res << stack.pop();
}
if (!stack.isEmpty() && stack.top() == '(')
{
stack.pop();
}
}
else if (ch == '+' || ch == '-')
{
while (!stack.isEmpty() && stack.top() != '(')
{
res << stack.pop();
}
stack.push(ch);
}
else if (ch == '*' || ch == '/')
{
while (!stack.isEmpty() && (stack.top() == '*' || stack.top() == '/'))
{
res << stack.pop();
}
stack.push(ch);
}
}
while (!stack.isEmpty())
{
res << stack.pop();
}
return res;
}
```
注意,上述代码中使用了QStack类来实现栈,需要包含头文件<QStack>。另外,考虑到表达式中可能有多位数字,需要对数字进行拼接处理。
阅读全文