输入前缀表达式,建立“表达式二叉树” ,并通过对此二叉树中序遍历: (1)求表达式的值 (2)输出(带必要括号的)中缀表达式 输入: -3-4 5 输出: 4 3 - ( 4 −5 )
时间: 2024-01-31 18:02:49 浏览: 105
为了建立表达式二叉树并求表达式的值,我们可以使用递归的方式进行操作。首先,我们需要定义一个二叉树节点的结构,其中节点的值可以是操作符或操作数。
```cpp
struct TreeNode {
std::string value;
TreeNode* left;
TreeNode* right;
};
```
然后,我们可以编写一个函数来构建表达式二叉树。该函数将使用前缀表达式来创建二叉树,并返回根节点。
```cpp
#include <iostream>
#include <stack>
#include <sstream>
bool isOperator(const std::string& value) {
return (value == "+" || value == "-" || value == "*" || value == "/");
}
bool isOperand(const std::string& value) {
std::istringstream iss(value);
double num;
return (iss >> num);
}
TreeNode* buildExpressionTree(const std::vector<std::string>& expression) {
std::stack<TreeNode*> stack;
for (int i = expression.size() - 1; i >= 0; i--) {
std::string token = expression[i];
TreeNode* newNode = new TreeNode;
newNode->value = token;
if (isOperand(token)) {
newNode->left = nullptr;
newNode->right = nullptr;
} else if (isOperator(token)) {
newNode->left = stack.top();
stack.pop();
newNode->right = stack.top();
stack.pop();
}
stack.push(newNode);
}
return stack.top();
}
```
接下来,我们可以编写一个函数来计算表达式的值,该函数将使用递归的方式通过遍历表达式二叉树来求解。
```cpp
double evaluateExpression(TreeNode* root) {
if (root == nullptr) {
return 0.0;
}
if (isOperand(root->value)) {
std::istringstream iss(root->value);
double num;
iss >> num;
return num;
}
double leftValue = evaluateExpression(root->left);
double rightValue = evaluateExpression(root->right);
if (root->value == "+") {
return leftValue + rightValue;
} else if (root->value == "-") {
return leftValue - rightValue;
} else if (root->value == "*") {
return leftValue * rightValue;
} else if (root->value == "/") {
if (rightValue != 0.0) {
return leftValue / rightValue;
} else {
std::cout << "Error: Division by zero!" << std::endl;
return 0.0;
}
}
return 0.0;
}
```
最后,我们可以编写一个函数来输出带必要括号的中缀表达式。该函数将使用递归的方式通过中序遍历表达式二叉树来生成中缀表达式。
```cpp
void printInfixExpression(TreeNode* root, bool isRoot = true) {
if (root == nullptr) {
return;
}
bool needParenthesis = !isRoot && isOperator(root->value);
if (needParenthesis) {
std::cout << "(";
}
printInfixExpression(root->left, false);
std::cout << " " << root->value << " ";
printInfixExpression(root->right, false);
if (needParenthesis) {
std::cout << ")";
}
}
```
现在,我们可以编写主函数,将输入的前缀表达式转换成字符串向量,并调用上述函数来完成所需的操作。
```cpp
int main() {
std::string input;
std::getline(std::cin, input);
std::istringstream iss(input);
std::vector<std::string> expression;
std::string token;
while (iss >> token) {
expression.push_back(token);
}
TreeNode* root = buildExpressionTree(expression);
double expressionValue = evaluateExpression(root);
std::cout << "表达式的值: " << expressionValue << std::endl;
std::cout << "中缀表达式: ";
printInfixExpression(root);
std::cout << std::endl;
return 0;
}
```
请注意,上述代码是一个基本的实现示例,仅能处理简单的四则运算。如果需要处理更复杂的运算符或其他操作,可能需要进一步调整代码。此外,代码中未包含错误处理逻辑,需要根据实际情况进行扩展。
阅读全文