表达式构建二叉树(中缀,前缀,后缀)

《数据结构与算法》上的一道作业题答案,本程序设计二叉树的构建,遍历以及打印等函数,能够实现自动分辨所输入表达式属于什么类型。

// TheRealBinaryTreeOfMine.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include<string>

#include<stack>

#include<queue>

#include<iostream>

#include<math.h>

using namespace std;

class BinaryNode{

public:

char date;

BinaryNode * leftchild;

BinaryNode * rightchild;

BinaryNode(){

date = 0;

leftchild = NULL;

rightchild = NULL;

}

BinaryNode(char ch){

date = ch;

leftchild = NULL;

rightchild = NULL;

}

};

int first_or_last(char a, char b); //判断两个运算符的优先级；

bool isOP(char ch); //判断该字符是否属于操作符； BinaryNode* Build_BinaryTree(BinaryNode* &BT, string str);//根据中缀表达式构建一颗二叉树； void Last(BinaryNode *bt); //后序遍历二叉树（递归）；

void First(BinaryNode *bt); //先序遍历二叉树（递归）；

void Inn(BinaryNode *bt); //中序遍历二叉树（递归）；

string Exp_turn(string s); //后缀表达式转换成中缀表达式；

string Exp_turn_and_turn(string s); //前缀表达式转换为中缀表达式；

int choice(char c, char d); //判断表达式属于什么类型的表达式（中缀，后缀，前缀）；

void Print(BinaryNode *bt); //打印二叉树（层序遍历，层层打印二叉树）；

int first_or_last(char a, char b){

if (a == '/' || a == '*'){

if (b == '+' || b == '-')

return 1;

if (b == '/' || b == '*')

return 0;

else

return 0;

}

if (a == '+' || a == '-'){

if (b == '+' || b == '-')

return 0;

if (b == '/' || b == '*')

return 0;

else

return 0;

}

else

《数据结构与算法》上的一道作业题答案,本程序设计二叉树的构建,遍历以及打印等函数,能够实现自动分辨所输入表达式属于什么类型。

return 0;

}

bool isOP(char ch)

{

string OP = { '+', '-', '*', '/', '(', ')' };

for (int i = 0; i < 6; i++){

if (ch == OP[i])

return true;

}

return false;

}

BinaryNode* Build_BinaryTree(BinaryNode* &BT, string str){

queue <BinaryNode*> aQ;

BinaryNode * root = BT;

if (str[0] == '('){

root = new BinaryNode(str[2]);

BT = new BinaryNode(str[1]);

BinaryNode *R = root;

aQ.push(BT);

int j = 3;

while (str[j] != '\0')

{

if (!isOP(str[j]))

{

BT = new BinaryNode(str[j]);

aQ.push(BT);

j++;

}

else

{

if (str[j] == ')' || str[j] == '(')

{

}

else

{

BT = new BinaryNode(str[j]);

root->leftchild = aQ.front();

//cout << root->leftchild->date;

root->rightchild = BT;

//cout << root->rightchild->date;

aQ.pop();

root = BT;

}

j++;

}

}

root->leftchild = aQ.front();

//cout << root->leftchild->date;

aQ.pop();

root->rightchild = aQ.front();

//cout << root->rightchild->date;

aQ.pop();

return R;

}

else{

root = new BinaryNode(str[1]);

BT = new BinaryNode(str[0]);

BinaryNode *R = root;

aQ.push(BT);

《数据结构与算法》上的一道作业题答案,本程序设计二叉树的构建,遍历以及打印等函数,能够实现自动分辨所输入表达式属于什么类型。

int j = 2;

while (str[j] != '\0')

{

if (!isOP(str[j]))

{

BT = new BinaryNode(str[j]);

aQ.push(BT);

j++;

}

else

{

if (str[j] == '(' || str[j] == ')')

{

}

else

{

BT = new BinaryNode(str[j]);

root->leftchild = aQ.front();

//cout << root->leftchild->date;

root->rightchild = BT;

//cout << root->rightchild->date;

aQ.pop();

root = BT;

}

j++;

}

}

root->leftchild = aQ.front();

//cout << root->leftchild->date;

aQ.pop();

root->rightchild = aQ.front();

//cout << root->rightchild->date;

aQ.pop();

return R;

}

}//中缀表达式构建了二叉树函数（消除了‘（’和‘）’）

void Last(BinaryNode *bt){

if (bt){

Last(bt->leftchild);

Last(bt->rightchild);

cout << bt->date;

}

}//后序遍历函数

void First(BinaryNode *bt){

if (bt){

cout << bt->date;

First(bt->leftchild);

First(bt->rightchild);

}

}//先序遍历函数

void Inn(BinaryNode *bt){

if (bt){

Inn(bt->leftchild);

cout << bt->date;

if (bt->rightchild)

{

if (isOP(bt->rightchild->date) && first_or_last(bt->date, bt->rightchild->date) == 1){ cout << "(";

《数据结构与算法》上的一道作业题答案,本程序设计二叉树的构建,遍历以及打印等函数,能够实现自动分辨所输入表达式属于什么类型。

Inn(bt->rightchild);

cout << ")"; //考虑root与root->leftchild操作符的优先级，如果root的优先级较大则需要添加小括号；

}

else

Inn(bt->rightchild);

}

}

}

string Exp_turn(string s){

queue <char> bQ;

stack <char> bS;

int k = 0;

while (s[k] != '\0'){

if (!isOP(s[k])){

bQ.push(s[k]);

}

else

{

bS.push(s[k]);

}

k++;

}

char ss[30];

int g = 0;

while (!bQ.empty())

{

ss[g] = bQ.front();

bQ.pop();

g++;

if (!bS.em …… 此处隐藏：3005字，全部文档内容请下载后查看。喜欢就下载吧 ……