P1175 表达式的转换 表达式二叉树做法
表达式二叉树（指针实现）做法
注：本做法中的二叉树使用了结构体，并且还使用了指针，理解起来可能略有不同之处。
题意简述
这道题告诉了我们一个中缀表达式，需要我们求出它的后缀表达式，并输出每步计算后的后缀表达式。
题目分析
个人认为用表达式二叉树来做会直观一些，就用表达式二叉树来做了。但是过程中有许多细节需要注意。
首先我们还是定义一下二叉树的节点：
struct ExpressionTree {
long long value = 0;
// 需要通过oper的指来判定节点类型
char oper = '\0';
ExpressionTree* left;
ExpressionTree* right;
// type为真的话，则这个节点为一个值
// type为否的话，则这个节点为一个运算符
ExpressionTree(bool type, char value) {
if(type) this->value = value - '0';
else this->oper = value;
}
// 析构函数
~ExpressionTree() {
if(oper = '\0') {
delete left;
delete right;
}
}
};如果oper为"\0"，那么这个节点就是一个值。
然后我们需要定义一个建树函数，这里我们给出其原型：
ExpressionTree* buildTree(int l, int r);这里的l和r分别表示字符串的左界和右界，表示计算这个区间内的中缀表达式的表达式二叉树。
基本思路
建立二叉树时，我们需要找到当前表达式中，那个最后被计算的运算符，然后分别求两边的表达式二叉树。只需要从中缀表达式的右边扫描到左边，先找加减法，找不到再找乘除法，最后找幂运算即可。
括号处理
我们还需要处理可能遇到的括号，保证最后处理的中缀表达式不是被包在括号内的。我们设定一个变量layers来表示目前的层数，如果layers为0，那么说明此时这个表达式没有被任何括号所包围，而运算符必须在第0层，否则它就不是最后被计算的（因为括号内的运算符总是被优先计算）。
我们从右边扫描到左边，如果遇到右括号")"就把层数+1，如果遇到左括号"("就把层数-1。扫描到运算符时必须要保证layers的值为0，这个运算符才有可能是最后运算的。如下输入中，最后一个运算符却是中间那个运算符：
24*5+(3+5)
如果这个表达式本身就被括号包围着呢？如果左右界的符号分别为"("和")"，此是这个表达式就有可能是被包围着的。这个时候我们需要判定从左扫到右边，layers的值是否在某一刻变为了0。如果没有变为0，则说明这个表达式被一个括号包围着，此时将左界右移一位，右界左移一位，重复上述检测，直到layers有可能变为0。如下输入中，该表达式就没有被包围：
(1+2)*(3*4)
实现代码如下：
// 判断整个表达式是否是被框在一个括号里
while(estr[l] == '(' && estr[r] == ')') {
// 层数，这里是从中间开始扫描的
int layers = 1;
bool flag = true;
for(int i = l + 1; i < r; i++) {
if(estr[i] == '(') layers++;
if(estr[i] == ')') layers--;
if(layers == 0) {
flag = false;
break;
}
}
if(flag)
l++, r--;
else
break;
}建树部分的具体代码将会在最下方给出。
输出处理
就是后序遍历嘛。
void printExpression(ExpressionTree* root) {
if(root->oper != '\0') {
printExpression(root->left);
printExpression(root->right);
printf("%c ", root->oper);
}
else printf("%lld ", root->value);
}节点合并计算
我们现在就要开始计算了，从根节点开始，每次先计算左子树，再计算右子树（我居然被这个坑到了）。每个节点计算完成时，删除它的两颗子树，把计算结果赋予给当前这个节点，并把这个节点的oper变量设置为"\0"，最后输出计算后的整颗二叉树的后序遍历。（可能有点绕），代码如下
// 合并一个表达式树为一个值
void merge(ExpressionTree* root) {
if(root->oper == '\0') return;
// 需要预先合并左右两边，注意需要先合并左边
merge(root->left);
merge(root->right);
int l = root->left->value;
int r = root->right->value;
if(root->oper == '+') root->value = l + r;
if(root->oper == '-') root->value = l - r;
if(root->oper == '*') root->value = l * r;
if(root->oper == '/') root->value = l / r;
if(root->oper == '^') root->value = pow(l, r);
// 把这个表达式树节点修改成值类型
delete root->left;
delete root->right;
root->oper = '\0';
// 输出每次合并后的后序遍历
printExpression(qroot); putchar('\n');
}AC代码
/* Headers */
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
/* Type and variables */
char estr[500];
int n;
struct ExpressionTree {
long long value = 0;
char oper = '\0';
ExpressionTree* left;
ExpressionTree* right;
// type为真的话，则这个节点为一个值
// type为否的话，则这个节点为一个运算符
ExpressionTree(bool type, char value) {
if(type) this->value = value - '0';
else this->oper = value;
}
// 析构函数
~ExpressionTree() {
if(oper = '\0') {
delete left;
delete right;
}
}
};
// 整个表达式树的指针
ExpressionTree* qroot;
/* Functions */
ExpressionTree* buildTree(int l, int r) {
// 判断整个表达式是否是被框在一个括号里
while(estr[l] == '(' && estr[r] == ')') {
// 层数，这里是从中间开始扫描的
int layers = 1;
bool flag = true;
for(int i = l + 1; i < r; i++) {
if(estr[i] == '(') layers++;
if(estr[i] == ')') layers--;
if(layers == 0) {
flag = false;
break;
}
}
if(flag)
l++, r--;
else
break;
}
// 这个时候应该是一个数字了
if(l == r) return new ExpressionTree(true, estr[l]);
int layers = 0; // 括号层数
// 找到最后一个被计算的运算符
for(int i = r; i >= l; i--) {
if(estr[i] == ')') layers++;
if(estr[i] == '(') layers--;
if((estr[i] == '+' || estr[i] == '-') && layers == 0) {
ExpressionTree* root = new ExpressionTree(false, estr[i]);
// 对运算符左右两边建树，下面同理
root->left = buildTree(l, i - 1);
root->right = buildTree(i + 1, r);
return root;
}
}
layers = 0;
for(int i = r; i >= l; i--) {
if(estr[i] == ')') layers++;
if(estr[i] == '(') layers--;
if((estr[i] == '*' || estr[i] == '/') && layers == 0) {
ExpressionTree* root = new ExpressionTree(false, estr[i]);
root->left = buildTree(l, i - 1);
root->right = buildTree(i + 1, r);
return root;
}
}
layers = 0;
for(int i = r; i >= l; i--) {
if(estr[i] == ')') layers++;
if(estr[i] == '(') layers--;
if(estr[i] == '^' && layers == 0) {
ExpressionTree* root = new ExpressionTree(false, estr[i]);
root->left = buildTree(l, i - 1);
root->right = buildTree(i + 1, r);
return root;
}
}
// 冗余情况，实际上没啥用，主要是为了过编译。
return new ExpressionTree(true, estr[l]);
}
// 后序遍历输出表达式树
void printExpression(ExpressionTree* root) {
if(root->oper != '\0') {
printExpression(root->left);
printExpression(root->right);
printf("%c ", root->oper);
}
else printf("%lld ", root->value);
}
int pow(int b, int p) {
int s = 1;
for(int i = 1; i <= p; i++)
s *= b;
return s;
}
// 合并一个表达式树为一个值
void merge(ExpressionTree* root) {
if(root->oper == '\0') return;
// 需要预先合并左右两边，注意需要先合并左边
merge(root->left);
merge(root->right);
int l = root->left->value;
int r = root->right->value;
if(root->oper == '+') root->value = l + r;
if(root->oper == '-') root->value = l - r;
if(root->oper == '*') root->value = l * r;
if(root->oper == '/') root->value = l / r;
if(root->oper == '^') root->value = pow(l, r);
// 把这个表达式树节点修改成值类型
delete root->left;
delete root->right;
root->oper = '\0';
// 输出每次合并后的后序遍历
printExpression(qroot); putchar('\n');
}
/* Main */
int main() {
scanf("%s", estr);
n = strlen(estr);
qroot = buildTree(0, n - 1);
printExpression(qroot); putchar('\n');
merge(qroot);
return 0;
}