简答题
偏难
#7424
表达式·表达式树·表达式求值 众所周知,任何一个表达式,都可以用一棵表达式树来表示。例如,表达式a+b*c,可以表示为如下的表达式树: + / \ a * /…
表达式·表达式树·表达式求值
众所周知,任何一个表达式,都可以用一棵表达式树来表示。例如,表达式a+b*c,可以表示为如下的表达式树:
+
/ \
a *
/ \
b c
现在,给你一个中缀表达式,这个中缀表达式用变量来表示(不含数字),请你将这个中缀表达式用表达式二叉树的形式输出出来。
时间限制:1000
内存限制:65535
输入
输入分为三个部分。 第一部分为一行,即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量(a-z),也可能含有运算符(+、-、*、/、小括号),不含有数字,也不含有空格。 第二部分为一个整数n(n < 10),表示中缀表达式的变量数。 第三部分有n行,每行格式为C x,C为变量的字符,x为该变量的值。
输出
输出分为三个部分,第一个部分为该表达式的逆波兰式,即该表达式树的后根遍历结果。占一行。 第二部分为表达式树的显示,如样例输出所示。如果该二叉树是一棵满二叉树,则最底部的叶子结点,分别占据横坐标的第1、3、5、7……个位置(最左边的坐标是1),然后它们的父结点的横坐标,在两个子结点的中间。如果不是满二叉树,则没有结点的地方,用空格填充(但请略去所有的行末空格)。每一行父结点与子结点中隔开一行,用斜杠(/)与反斜杠(\)来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格,\出现的横坐标位置为父结点的横坐标偏右一格。也就是说,如果树高为m,则输出就有2m-1行。 第三部分为一个整数,表示将值代入变量之后,该中缀表达式的值。需要注意的一点是,除法代表整除运算,即舍弃小数点后的部分。同时,测试数据保证不会出现除以0的现象。
样例输入
a+b*c 3 a 2 b 7 c 5
样例输出
abc*+ + / \ a * / \ b c 37
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码!
#include<iostream>
#include<string>
#include <cstring>
#include<cmath>
#include<stack>
#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><p><br/></p>
这道题暂未补解析。