描述
眾所周知，任何一個運算式，都可以用一棵運算式樹來表示，例如，運算式a+b*c，可以表示為如下的運算式樹：
???+
??/??\
?a????*
?????/??\
?????b??c
現在，給你一個中綴運算式，這個中綴運算式用變數來表示（不含數字），請你將這個中綴運算式用運算式二叉樹的形式輸出出來，
輸入
輸入分為三個部分，
第一部分為一行，即中綴運算式(長度不大于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
中綴運算式生成二叉樹
- 考慮沒有括號的情況
對于一個中綴運算式：\(a+b\),由運算子分為左右兩個部分，其二叉樹表示形式自然為：
所以，構建一個運算式樹，關鍵在于找到運算式的根結點，然后分左右兩個部分構建樹；拓展到多個同級運算子的運算式：\(a+b+c+...+n\),可以這樣構建其運算式樹：
- 找到最后運算的結點,若以最右邊的一個+為根結點
- 以根結點分為左右兩個部分
- 構建根結點，左邊構建樹，右邊構建樹
- 若左邊部分又是一個運算式，執行1、2、3步驟
- 若右邊部分又是一個運算式，執行1、2、3步驟
這樣就可以構建出整個運算式樹：
graph TB root((+))---left[a+b+...+n-1] root((+))---right((n)) left-.->|左邊部分又是一個運算式|root_l subgraph root_l((+))---left_l[a+b+...+n-2] root_l((+))---right_l((n-1)) end left_l-.->|n-1次重復后|root_n subgraph root_n((+))---left_n((a)) root_n((+))---right_n((b)) end- 考慮有不同優先級運算子的情況：
\(a+b*c\)，因為+是最后運算，所以它一定是樹的根，*先運算，是+號分得的右邊部分的根，這樣得到其運算式樹：
所以，含有優先級不同的運算式，關鍵在于找到運算式最后運算的運算子，作為某個運算式樹的根，然后分左右兩個部分構建樹；同樣，同級運算子以最左邊的運算子為最后運算的運算子，統一第一種情況：拓展到多個不同運算子出現的情況:\(a+b*c p_1...p_k n(p_i為第i個運算子)\)
- 找到最后運算的運算子作為根結點
- 以根結點分為左右兩個部分
- 構建根結點，左邊構建樹，右邊構建樹
- 若左邊部分又是一個運算式，執行1、2、3步驟
- 若右邊部分又是一個運算式，執行1、2、3步驟
這樣就可以構建出整個運算式樹：
graph TB root((+))---left((a)) root((+))---right[b*c p_1...p_k n] right-.->|右邊邊部分又是一個運算式|root_r subgraph 若p_i是最后運算的運算子 root_r((p_i))---left_r[b*c p_1...p_i-1 n-k+i-1] root_r((p_i))---right_r[n-k+i p_i+1...p_k n] end- 考慮存在括號的情況
如果運算式中存在括號，最后運算的運算子一定在括號外，這樣，需要一個變數記錄括號位置，在括號外找到最后運算的運算子，然后分為左右兩個部分，重復找括號，建樹操作就可以了，以\(a*b+(c+d)\)為例:
- 找到最后運算的+號分左右兩個部分：\(a*b\)和\((c+d)\)
- 左邊部分建樹
- 右邊部分建樹：
- 右邊部分括號外找不到最后運算的運算子，說明整個運算式被括號括起來
- 去掉括號：c+d 建樹
- 若左邊部分又是一個運算式，執行1、2、3步驟
- 若右邊部分又是一個運算式，執行1、2、3步驟
所以，構建運算式樹的函式:CreateExpressionTree(char *expression, int start, int end, Bitree &tree)中，傳入了運算式的開始下標和結尾下標，方便分割左邊和右邊部分：
CreateExpressionTree(char *expression, int start, int end, Bitree &tree)函式：
void CreateExpressionTree(char *expression, int start, int end, Bitree &tree)
{
/**
* 這里，c1用來記錄括號外最后運算的+或-
* c2用來記錄括號外最后運算的+或-
* p記錄括號當讀到一個（ p++, ） 時 p--, 只有p==0時才說明c1, c2
* 括號外
*/
int i, c1 = -1, c2 = -1, p = 0;
if (end - start == 1) {
//只有一個結點，直接建立結點
tree = new BTNode;
tree->data = https://www.cnblogs.com/levarz/p/*(expression+start);
tree->left_child = tree->right_child = NULL;
return;
}
for (i = start; i < end; i++) {
switch (*(expression+i))
{
case'(': p++; break;
case ')': p--; break;
case '+': case '-': if (!p) c1 = i; break;
case '*': case '/': if (!p) c2 = i; break;
}
}
//c1 < 0，說明括號外沒有第一優先級的+或者-，那么就只能考慮*或者/
if (c1 < 0) c1 = c2;
// 說明括號外沒有第一優先級的*或者/，說明此時運算式被括號括起來, 去掉括號后建樹
if (c1 < 0) CreateExpressionTree(expression,start+1,end-1,tree);
else {
//建立根
CreateExpressionTree(expression,c1,c1 + 1,tree);
//建立左樹
CreateExpressionTree(expression,start,c1,tree->left_child);
//建立右樹
CreateExpressionTree(expression,c1+1,end,tree->right_child);
}
}
對于建樹這一部分，參考了運算式樹與前中后綴運算式,詳細訪問鏈接
列印運算式樹
如題：
如果該二叉樹是一棵滿二叉樹，則最底部的葉子結點，分別占據橫坐標的第1、3、5、7……個位置（最左邊的坐標是1），然后它們的父結點的橫坐標，在兩個子結點的中間，如果不是滿二叉樹，則沒有結點的地方，用空格填充（但請略去所有的行末空格），每一行父結點與子結點中隔開一行，用斜杠（/）與反斜杠（\）來表示樹的關系，/出現的橫坐標位置為父結點的橫坐標偏左一格，\出現的橫坐標位置為父結點的橫坐標偏右一格，也就是說，如果樹高為m，則輸出就有2m-1行，
用一個graph[MAX_ROW][MAX_COL] 陣列保存運算式樹的位置資訊，以題例來看：
???+
??/??\
?a????*
?????/??\
?????b??c
首先，一共有\(2^h-1\)個結點,層層找結點位置，中間位置，即第\(2^{h-1}\)個結點+把該層分為兩個部分，且左右部分皆是\(2^{h-2}\)長度(ps:因為包含了\/的位置），如果有左結點，左結點就在\(2^{h-2}\)的中間部分，(ps:這里由于用到了\(2^x\)次方，在宏定義了一個POW(NUM) 1 << NUM, 1 << NUM 即右移NUM,即\(2^{NUM}\))右結點也如此處理...這樣，處理下一層時，也如同上一層處理:先處理根結點，在處理左右結點，在處理完根結點后下一層應該留給/\，位置為中間位置左偏一個或右偏一個；
void Print(Bitree root, int row, int col, int len)
{
if (root == NULL) return;
graph[row][col-1] = root->data; //當前層中間位置
if (root->left_child!=NULL) {
graph[row+1][col-2] = '/'; //下一層留給/，中間位置偏左一個
Print(root->left_child,row+2,col-len,len>>1); // 左邊部分
}
if (root->right_child!=NULL) {
graph[row+1][col] = '\\';
Print(root->right_child,row+2,col+len,len>>1);
}
}
對于列印運算式樹這一部分，參考了運算式·運算式樹·運算式求值,詳細訪問鏈接
計算部分
對于這一部分，由于已經有了運算式樹了，只需要一層層求解即可:
- 如果結點是運算子,將左樹和右樹的計算結果和根運算
- 如果結點不是運算子，直接回傳變數值
其中左樹和右樹的計算結果就是一個遞回程序，反復執行1、2步；
這一部分由于要用到變數的值， 使用了 map<char,int> to_value的一個映射,給一個結點變數，對應一個變數值
對于計算部分，參考了運算式·運算式樹·運算式求值,詳細訪問鏈接
其它
其他部分根據題意求解即可,關于運算式輸入，使用了一個char*指標，但是我在這個地方初始化 expression = new char [52];一開始記成 expression = new char （52）;導致一直不能過...
完整代碼
/*
@File : expression_tree.cpp
@Time : 2020/04/27
@Desc : 運算式·運算式樹·運算式求值
*/
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <map>
#define POW(NUM) 1<<NUM
#define MAX_ROW 70
#define MAX_COL 300
using namespace std;
typedef struct BTNode
{
char data;
struct BTNode *left_child;
struct BTNode *right_child;
}*Bitree;
char graph[MAX_ROW][MAX_COL];
map <char,int> to_value;
void CreateExpressionTree(char *expression, int start, int end, Bitree &tree)
{
int i, c1 = -1, c2 = -1, p = 0;
if (end - start == 1) {
tree = new BTNode;
tree->data = https://www.cnblogs.com/levarz/p/*(expression+start);
tree->left_child = tree->right_child = NULL;
return;
}
for (i = start; i < end; i++) {
switch (*(expression+i))
{
case'(': p++; break;
case ')': p--; break;
case '+': case '-': if (!p) c1 = i; break;
case '*': case '/': if (!p) c2 = i; break;
}
}
if (c1 < 0) c1 = c2;
if (c1 < 0) CreateExpressionTree(expression,start+1,end-1,tree);
else {
CreateExpressionTree(expression,c1,c1 + 1,tree);
CreateExpressionTree(expression,start,c1,tree->left_child);
CreateExpressionTree(expression,c1+1,end,tree->right_child);
}
}
void PostOrder(Bitree tree)
{
if (tree == NULL) return;
PostOrder(tree->left_child);
PostOrder(tree->right_child);
cout << tree->data;
}
int GetHeight(Bitree tree)
{
int left_height, right_height;
if (tree == NULL) return 0;
else {
left_height = GetHeight(tree->left_child);
right_height = GetHeight(tree->right_child);
return (left_height > right_height)?(left_height+1):(right_height+1);
}
}
void Print(Bitree root, int row, int col, int len)
{
if (root == NULL) return;
graph[row][col-1] = root->data;
if (root->left_child!=NULL) {
graph[row+1][col-2] = '/';
Print(root->left_child,row+2,col-len,len>>1);
}
if (root->right_child!=NULL) {
graph[row+1][col] = '\\';
Print(root->right_child,row+2,col+len,len>>1);
}
}
int Calculate(Bitree tree)
{
switch (tree->data)
{
case '+':
return Calculate(tree->left_child) + Calculate (tree->right_child);
break;
case '-':
return Calculate(tree->left_child) - Calculate (tree->right_child);
break;
case '*':
return Calculate(tree->left_child) * Calculate (tree->right_child);
break;
case '/':
return Calculate(tree->left_child) / Calculate (tree->right_child);
break;
default:
return to_value[tree->data];
break;
}
}
int main(int argc, char const *argv[])
{
int n, value;
char *expression, valuable;
Bitree tree;
// expression = (char*)malloc(sizeof(char)*52);
// expression = new char(52); !!!!!
expression = new char[52];
cin >> expression;
cin >> n;
while (n--) {
cin >> valuable >> value;
to_value[valuable] = value;
}
CreateExpressionTree(expression,0,strlen(expression),tree);
PostOrder(tree); cout << endl;
memset(graph,' ',sizeof(graph));
Print(tree,0,POW(GetHeight(tree)-1),POW(GetHeight(tree)-2));
int j = 0, l = 0;
for (int i = 0; i < MAX_ROW; ++i) {
j = MAX_COL - 1;
while (j >= 0 && graph[i][j] == ' ') --j;
if (j > -1) {
++l;
graph[i][j+1] = '\0';
}
else break;
}
for (int i = 0; i < l; ++i) cout << graph[i] << endl;
cout << Calculate(tree) << endl;
system("pause");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30652.html
標籤：C++
下一篇：博弈--尼姆博弈