Question

急求一道C++编程问题解答！！！！

期末上机考试题目，2选一，一个是复制二叉树，一个是算术表达式求值（栈应用）。求高人帮我写下程序代码以及每个步骤的说明和讲解，越详细越好。谢谢！！！！急用！！！
貌似有问题啊，好多错误

Answer 1

算数表达式
这是核心
//task.h文件
#ifndef _TASK_H_
#define _TASK_H_

#define novalue -1
#define OPTER "+-*/();"
#define MATH "0123456789+-*/();"

//extern int opters[5];

typedef struct node node_t;
struct node {
int value;
node_t* pre;
};

typedef struct stack stack_t;
struct stack {
node_t* sp;
int size;
};

void push(stack_t* stk,node_t* nd);
int pop(stack_t* stk);
void clearstack(stack_t* stk);
void print_d(int value);
void print_c(int value);

#endif
-------------------------------------------------------------------

//task.c文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "task.h"

int opters[5] = {'+','-','*','/'};
void push(stack_t* stk,node_t* nd){
if (stk->sp == NULL) {
stk->sp = nd;
} else {
nd->pre = stk->sp;
stk->sp = nd;
}
stk->size++;
}

int pop(stack_t* stk){
if (stk->sp == NULL){
return novalue;
}else {
int ret = stk->sp->value;
stk->sp = stk->sp->pre;
stk->size--;
return ret;
}
}

void clearstack(stack_t* stk){
while (stk->sp)
pop(stk);
}

void print_d(int value){
printf("%d\n",value);
}
void print_c(int value){
printf("%c\n",value);
}

void ergod(stack_t* stk,void (*doit)(int)) {
node_t* index = stk->sp;
while (index){
if (doit)
doit(index->value);
index = index->pre;
}
}

//return 0 no math
//return 1 is math
int ismath(const char* str){
while (*str){
if (!strchr(MATH,*str))
return 0;
str++;
}
return 1;
}

int getopnd(char** opnd){
int ret = atoi(*opnd);
char* tmp = NULL;
if (tmp = strpbrk(*opnd,OPTER)){
*opnd = tmp;
} else {
*(*opnd) = 0;
}
return ret;
}

int getoptr(char** optr){
int ret = -1;
if (strlen(*optr))
ret = **optr;
(*optr)++;
return ret;
}

node_t* popdem = NULL;

int opercmp(stack_t* stk,int value){
int i,j;
for (i = 0; i < 5; i++){
if (opters[i] == value)
break;
}
if (stk->sp == NULL)
return 1;

for (j = 0; j < 5; j++){
if (opters[j] == stk->sp->value)
break;
}
if (stk->sp->value == '(') {
if (value == ')')
return 0;
else
return 1;
}
if (value == '(')
return 1;
if (value == ')')
return -1;
if ((stk->sp->value == '+' || stk->sp->value == '-') && (value == '*' || value == '/'))
return 1;
return -1;

}

int operate(int left, int right, int opt){
printf("%d %c %d\n",left,opt,right);
switch (opt) {
case '+':
return (left + right);
case '-':
return (left - right);
case '*':
return (left * right);
case '/':
return (left / right);
}
}

void add(stack_t* stk_opr,stack_t* stk_opnd,int or){
int tmppro = opercmp(stk_opr,or);
if (tmppro > 0) {
node_t* ndr = (node_t*)malloc(sizeof(node_t));
ndr->value = or;
ndr->pre = NULL;
push(stk_opr,ndr);
} else if (tmppro < 0) {
if (stk_opnd->size > 1) {
int a = pop(stk_opnd);
int b = pop(stk_opnd);
int opt = pop(stk_opr);
int result = operate(b,a,opt);

node_t* ndo = (node_t*)malloc(sizeof(node_t));
ndo->value = result;
ndo->pre = NULL;
push(stk_opnd,ndo);

add(stk_opr,stk_opnd,or);
} else {
node_t* ndr = (node_t*)malloc(sizeof(node_t));
ndr->value = or;
ndr->pre = NULL;
push(stk_opr,ndr);
}
} else {
pop(stk_opr);
}
}

void process(stack_t* stk_opnd,stack_t* stk_opr,char* tmp){
while (strlen(tmp)){
if (ismath(tmp)){
int on = -1;
int or = -1;
if (isdigit(*tmp)) {
on = getopnd(&tmp);
node_t* ndp = (node_t*)malloc(sizeof(node_t));
ndp->value = on;
ndp->pre = NULL;
push(stk_opnd,ndp);
} else if (strchr(OPTER,*tmp)) {
or = getoptr(&tmp);
if (stk_opr->sp){
add(stk_opr,stk_opnd,or);
}else{
node_t* ndr = (node_t*)malloc(sizeof(node_t));
ndr->value = or;
ndr->pre = NULL;
push(stk_opr,ndr);
}
}
} else {
printf("error\n");
}
}
}

int listener(){
//printf("\033[2J");
stack_t* stk_opnd = (stack_t*)malloc(sizeof(stack_t));
stk_opnd->sp = NULL;
stk_opnd->size = 0;

stack_t* stk_opr = (stack_t*)malloc(sizeof(stack_t));
stk_opr->sp = NULL;
stk_opr->size = 0;

char* tmp = (char*)calloc(1000,sizeof(char));
char* freetmp = tmp;

while (1){
tmp = freetmp;
memset(tmp,0,1000);
printf("consle@%s# ",__DATE__);
scanf("%s",tmp);
//gets(tmp);task.c:(.text+0x633): warning: the `gets' function is dangerous and should not be used.
if (strlen(tmp) == 0)
printf("not command!\n");
else if (!strcmp("exit",tmp)){
printf("bye!\n");
break;
} else if (!ismath(tmp)){
printf("not command!\n");
} else {
printf("%s\n",tmp);
process(stk_opnd,stk_opr,tmp);
printf("-----------------------\n");
ergod(stk_opnd,print_d);
printf("-----------------------\n");
ergod(stk_opr,print_c);
printf("-----------------------\n");
clearstack(stk_opnd);
clearstack(stk_opr);
}
}
free(freetmp);
}
//2*3/6-2*(3-4*((4+2)/6));

//main.c这是执行文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "task.h"

int main(){
listener();
return 0;
}

//makefile文件
exec = main huffman3 offset
.PHONY:all clean
all:${exec}
main:task.h task.c
clean:
rm -fr ${exec} *.~ *.swp

复制二叉树的你没说清楚
如果只是把一个二叉树复制一遍那好办
采用二叉树前序遍历，遍历到一个节点然后新增到一个新树里去，就是这个思路