1 Star 0 Fork 0

骆谦实(lkh) / PTA--博客作业相关题目集

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
克隆/下载
6-4 jmu-ds-表达式树 (25 分) 5.61 KB
一键复制 编辑 原始数据 按行查看 历史
#include<iostream>
#include<string>
#include<stack>
using namespace std;
typedef struct BiTNode{ //二叉树的二叉链表存储表示
char data;
struct BiTNode *lchild,*rchild;
}BTNode,*BTree;
void InitExpTree(BTree &T,string str) ; //建二叉表达式树
double EvaluateExTree(BTree T);//计算表达式树
char Precede(char t1,char t2) ;//比较t1,t2运算符优先级函数
int In(char c) ;//判断c是否运算符
void CreateExpTree(BTree &T,BTree a,BTree b,char ch);//建简单二叉树
void DestroyBTree(BTree bt);//销毁树
int main()
{
string str;
BTree T;
getline(cin,str);
InitExpTree(T,str); //创建表达式树
cout<<EvaluateExTree(T); //输出值
DestroyBTree(T);
return 0;
}
char Precede(char t1,char t2)
{ /*判断两符号的优先关系 */
char f;
switch(t2)
{
case '+': if(t1=='('||t1=='#') f='<';
else f='>';
break;
case '-': if(t1=='('||t1=='#') f='<';
else f='>';
break;
case '*':if(t1=='*'||t1=='/'||t1==')') f='>';
else f='<';
break;
case '/':if(t1=='*'||t1=='/'||t1==')') f='>';
else f='<';
break;
case '(': if(t1!=')') f='<';
break;
case')': if(t1=='(') f='=';
else f='>';
break;
case'#': if(t1=='#') f='=';
else f='>';
}
return f;
}
int In(char c)
{ /* 判断c是否为运算符 */
switch(c)
{
case '+':
case'-':
case'*':
case '/':
case'#':
case '(':
case')':return 1;break;
default:return 0;
}
}
void CreateExpTree(BTree &T,BTree a,BTree b,char ch)
{ //简单二叉树的创建
T=new BTNode;
T->data=ch;
T->lchild=a;
T->rchild=b;
}
void DestroyBTree(BTree bt)//销毁树
{
if(bt!=NULL)
{
DestroyBTree(bt->lchild);
DestroyBTree(bt->rchild);
delete bt;
}
}
void InitExpTree(BTree& T, string str)//建表达式的二叉树
{
stack<BTree> numberStack;/*储存分支结点,或者说操作数的栈*/
stack<BTree> signStack;/*储存根结点,或者说运算符的栈*/
char cur_char;
/*优先遍历输入的字符串*/
for (int i = 0; i < str.size(); i++)
{
cur_char = str[i];
if (In(cur_char))
{
while (1)
{
if (signStack.empty()
|| Precede(signStack.top()->data, cur_char) == '<')/*入栈的条件判断*/
{
BTree signTNode = new BiTNode;
signTNode->data = cur_char;
signStack.push(signTNode);
/*运算符入栈是该运算符流程结束的标志之一*/
break;
}
else if (Precede(signStack.top()->data, cur_char) == '>')/*出栈的条件判断*/
{
char sign = signStack.top()->data;
signStack.pop();
BTree newNumb;
BTree rTree = numberStack.top();
numberStack.pop();
BTree lTree = numberStack.top();
numberStack.pop();
/*然后开始建一个小二叉树*/
CreateExpTree(newNumb, lTree, rTree, sign);
numberStack.push(newNumb);
}
else if (Precede(signStack.top()->data, cur_char) == '=')
{
signStack.pop();
break;
}
}
}
else/*cur_char为数字*/
{
BTree numbTNode = new BiTNode;
numbTNode->data = cur_char;
numbTNode->lchild = NULL;
numbTNode->rchild = NULL;
numberStack.push(numbTNode);
}
}
if (signStack.empty())
{
T = numberStack.top();
return;
}
else
{
while (!signStack.empty())
{
char sign = signStack.top()->data;
signStack.pop();
BTree newNumb;
BTree rTree = numberStack.top();
numberStack.pop();
BTree lTree = numberStack.top();
numberStack.pop();
/*然后开始建一个小二叉树*/
CreateExpTree(newNumb, lTree, rTree, sign);
numberStack.push(newNumb);
}
T = numberStack.top();
return;
}
}
double EvaluateExTree(BTree T)//计算表达式树
{
if (T == NULL)
{
return 0;/*该数字并未被利用*/
}
if (In(T->data))
{
switch (T->data)
{
case '+':
return EvaluateExTree(T->lchild) + EvaluateExTree(T->rchild);
case '-':
return EvaluateExTree(T->lchild) - EvaluateExTree(T->rchild);
case '*':
return EvaluateExTree(T->lchild) * EvaluateExTree(T->rchild);
case '/':
if (EvaluateExTree(T->rchild) == 0)
{
cout << "divide 0 error!" << endl;
exit(0);/*直接退出程序*/
}
else
{
return EvaluateExTree(T->lchild) / EvaluateExTree(T->rchild);
}
default:
break;
}
}
else/*当结点值为数字的时候*/
{
return ((double)T->data - '0');
}
}
C++
1
https://gitee.com/luoqianshi/linear-table-programming.git
git@gitee.com:luoqianshi/linear-table-programming.git
luoqianshi
linear-table-programming
PTA--博客作业相关题目集
master

搜索帮助