我是一个 c++ 学习者,我正在尝试为此表达式创建一个 BST 树:2346*+/8+,并执行中序和后序以获得表达式的修复版本和后修复版本。我很难为表达式创建二叉树。这是我的比索代码:
Tree:
Stack:
inorder fn{}
postorder fn{}
main{
input the file;
while(expression){
if(digit){
s.push}
else if(operator){
s.top = right;
s.pop;
s.top = left;
s.pop;
T1 = new Tree(operator, left, right);
}
}
我要创建的树是这样的
+
/ \
(/) 8
/ \
+ 2
/ \
* 3
/ \
4 6
此代码的问题是在创建 (4*6) 树之后,我无法将 (+3) 链接到 (4*6)。请帮助我。
感谢 Drew McGowen,我更新了我的代码,现在我将 4*6 树推回堆栈,这是代码:
while(input_file >> expression){
if(isdigit(expression[0])){
sscanf(expression,"%c",&digit);
printf("reading a number: %c \n",digit);
Tree* s.push(digit);
}
else {
sscanf(expression,"%c",&oper);
printf("reading an operator: %c \n",oper);
T1 = new Tree(s.top(), NULL, NULL);
s.pop();
T2 = new Tree(s.top(), NULL, NULL);
s.pop;
myTree = new Tree(oper, T1, T2);
s.push(myTree);
我不断收到错误消息,有人可以帮我检查一下代码吗?谢谢大家。
大家好,我认为主要部分是在正确的轨道上,但我应该如何修改堆栈函数以接受树?这是我的堆栈函数:
void Stack::Push(char newthing) {
index++;
data[index] = newthing;
}
void Stack::Pop() {
if (index > -1) { index--; }
}
char Stack::Top() {
return data[index];
最佳答案
您的堆栈似乎包含数字。为了将后缀表示法中的表达式解析为堆栈,堆栈应包含树元素。
伪代码:
main{
input the file;
while(expression){
if(digit){
s.push(new Tree(digit)); //create leaf-element
}
else if(operator){
Tree tr = s.pop();
Tree tl = s.pop();
T1 = new Tree(operator,tl,tr);
}
}
这或多或少也是 L(AL)R 解析器的工作方式。
关于您的代码:
- 您应该将顺序颠倒到
T2
和T1
,因为您是从堆栈中弹出; T1
和T2
应该是简单的弹出操作,没有构造函数调用;和你应该构建一个数字大小写的树节点(叶子)。
while(input_file >> expression){ if(isdigit(expression[0])){ sscanf(expression,"%c",&digit); printf("reading a number: %c \n",digit); s.push(new Tree(digit,NULL,NULL)); //create new leaf } else { sscanf(expression,"%c",&oper); printf("reading an operator: %c \n",oper); T2 = s.top(); //T2 instead of T1 and simple pop s.pop(); T1 = s.top(); //T1 instead of T2 and simple pop s.pop; myTree = new Tree(oper, T1, T2); s.push(myTree); } }
如果输入流是有效的(例如不是 1+
或 12+6
),结果是一个包含一个元素的堆栈:表达式树。
关于c++ - 如何为算术表达式创建 BST,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27956645/