答案:<pre class="brush:cpp;toolbar:false">#include <cmath>
#include <cstring>
#include <iostream>
#include <stack>
#include <string>
#define OK 1
#define ERROR 0
#define MAXSIZE 50
using namespace std;
struct number {
char ch;
int value;
};
number a[10];
// 定义二叉树类型
typedef struct BiNode {
char date;
struct BiNode *lchild, *rchild;
} BiNode;
// 定义栈类型
typedef struct SqStack {
char *base;
char *top;
int stacksize;
} SqStack;
// 初始化栈
int InitStack(SqStack &S) {
S.base = new char[MAXSIZE];
if (!S.base)
exit(ERROR);
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
// 出栈
char Pop(SqStack &S) {
if (S.top == S.base)
return ERROR;
char e = *(--S.top);
return e;
}
// 入栈
int Push(SqStack &S, char e) {
if (S.top - S.base == S.stacksize)
return ERROR;
*(S.top++) = e;
return OK;
}
// 将中缀表达式转化为后缀表达式
string Change(string str) {
// str为中缀表达式,str2为后缀表达式
string str2 = "";
char ch, e; // e用于保存栈中弹出的元素
SqStack S1; // S1用于存放操作符(为辅助栈),S用于存放后续表达式
InitStack(S1);
for (int i = 0; i < str.size(); i++) {
ch = str[i];
if (ch >= 'a' && ch <= 'z') {
str2 += ch;
}
if (ch == '(')
Push(S1, ch);
if (ch == ')') {
while (*(S1.top - 1) != '(') {
e = Pop(S1);
str2 += e;
}
Pop(S1); // 左括号出栈但不入S2栈中
}
// 遇到+或-时
// 栈空/栈顶为左括号:直接入栈
// 否则一直出栈,直到栈空/栈顶为左括号,再入栈
if (ch == '+' || ch == '-') {
while (*(S1.top - 1) != '(' && S1.base != S1.top) {
e = Pop(S1);
str2 += e;
}
Push(S1, ch);
}
// 遇到*或/时
// 栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈
// 否则一直出栈,直到满足上述条件,再入栈
if (ch == '*' || ch == '/') {
while (S1.base != S1.top && *(S1.top - 1) != '(' &&
*(S1.top - 1) != '-' && *(S1.top - 1) != '+') {
e = Pop(S1);
str2 += e;
}
Push(S1, ch);
}
}
// 中缀表达式遍历完成,还需检查栈中是否有未输出字符
// 判断栈空,非空则直接出栈
while (S1.base != S1.top) {
e = Pop(S1);
if (e != '(')
str2 += e;
}
return str2;
}
struct BiNode *s[MAXSIZE]; // 定义栈,该栈用于存放树
int top = -1;
// 建立二叉树
BiNode *CreatTree(string str) {
// str为后缀表达式
BiNode *T, *T2;
SqStack S;
BiNode *e1, *e2;
int i;
InitStack(S);
for (i = 0; i < str.size() - 1; i++) {
if (str[i] >= 'a' && str[i] <= 'z') {
T = new BiNode;
T->date = str[i];
T->lchild = T->rchild = NULL;
s[++top] = T;
} else {
T = new BiNode;
T->date = str[i];
e1 = s[top--];
e2 = s[top--];
T->lchild = e2;
T->rchild = e1;
s[++top] = T;
}
}
T = new BiNode;
T->date = str[i];
T->rchild = s[top--];
T->lchild = s[top--];
s[++top] = T;
T2 = new BiNode;
T2 = s[top];
return T2;
}
int Seek(char e, int n) {
for (int i = 0; i < n; i++) {
if (a[i].ch == e)
return a[i].value;
}
}
int Count(string str, int n) {
// str为后缀表达式数组,n变量个数
int sum = 0;
stack<int> S;
int x, x1, x2;
for (int i = 0; i < n; i++) {
cin >> a[i].ch >> a[i].value;
}
for (int i = 0; i < str.size(); i++) {
if (str[i] >= 'a' && str[i] <= 'z') {
x = Seek(str[i], n);
S.push(x);
} else {
x2 = S.top();
S.pop(); // 左操作数
x1 = S.top();
S.pop(); // 右操作数
switch (str[i]) {
case '+':
sum = x1 + x2;
break;
case '-':
sum = x1 - x2;
break;
case '*':
sum = x1 * x2;
break;
case '/':
sum = x1 / x2;
break;
}
S.push(sum);
}
}
sum = S.top();
return sum;
}
char arr[1000][1000];
// 打印二叉树
void PrintTree(int tag, BiNode *T, int x, int m, int y) {
arr[2 * tag - 1][(x + m) / 2] = T->date;
if (tag != 1) {
if (y == 1)
arr[2 * tag - 2][m] = '/';
else
arr[2 * tag - 2][x] = '\\';
}
if (T->lchild != NULL)
PrintTree(tag + 1, T->lchild, x, (x + m) / 2 - 1, 1);
if (T->rchild != NULL)
PrintTree(tag + 1, T->rchild, (x + m) / 2 + 1, m, 0);
}
// 计算二叉树的深度
int Depth(BiNode *T) {
int m, n;
if (T == NULL)
return 0;
else {
m = Depth(T->lchild);
n = Depth(T->rchild);
if (m > n)
return (m + 1);
else
return (n + 1);
}
}
bool Judge(int i, int j, int n) {
for (int k = j + 1; k <= n; k++) {
if (arr[i][k] != ' ')
return 1;
}
return 0;
}
int main() {
string str1; // 中序表达式
cin >> str1;
int n; // 变量个数
cin >> n;
string str2 = Change(str1); // str2为后序表达式
BiNode *T = CreatTree(str2);
int sum = Count(str2, n);
int dp = Depth(T);
cout << str2 << endl;
memset(arr, ' ', sizeof(arr));
PrintTree(1, T, 1, pow(2.0, dp) - 1, 0);
for (int i = 1; i <= 2 * dp - 1; i++) {
for (int j = 1; j <= pow(2.0, dp) - 1; j++) {
cout << arr[i][j];
if (arr[i][j] != ' ') {
if (Judge(i, j, pow(2.0, dp) - 1))
continue;
else
break;
}
}
cout << endl;
}
cout << sum << endl;
return 0;
}</pre>
这道题暂未补解析。