uva 112 Tree Summing

点击打开链接

题目意思：给定一个字符串，把字符串里面的数字建成一颗树，数字有可能是负号，所以这一题其实有很多可以学的，比如怎样输入会有多行，还有怎么建立一颗树，等等。

解题思路：我们用一个字符数组来存储读入的字符串，用一个栈来存储括号，判断如果栈为空并且读到换行那么就退出。我们可以先把根节点建好，建根节点调用creatnode()函数，注意数字可能是1234    -1234这些情况，所以判断.然后我们在从根节点后面的位置开始变量字符数组，如果是（‘（’）则判断下一额是数字还是右括号，如果是数字则continue，如果是右括号则，执行creatnode()函数产生新的节点。中间数字有可能是多位的情况，所以要做好处理，即传入creatnode()的参数要做好。树建好以后就是搜素路径和是否为sum，我们用深搜来处理，（中间可以用前序遍历来判断是否建好了树），我们知道对于叶子节点，那么它的两个子树的al都是Min,所以在搜索时候处理做好即可。

代码：

#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <stack>
#include <list>
#include <algorithm>
using namespace std;

const int Min = -999999999;//定义一个宏为无穷小，后面遇到左括号后面没有数字时要处理
char ch , c[50000];//字符数组存储字符串
int sum, tempsum, mark, cmark, Found , len;
stack<char>st;//栈存储括号
//二叉树的结构体
struct node {
    int val;
    struct node *lchild, *rchild, *father;//用一个father指针来指向当前指针cur的父亲节点
};
node *root, *temp, *cur;

//初始化函数用来对每一个node 指针初始化
void init(node *u , int m) {
    u -> father = NULL;
    u -> lchild = NULL;
    u -> rchild = NULL;
    u -> val = m;
}
//建立新的节点
void createnode(int n) {
    temp = new node;
    init(temp , n);//初始化temp，临时的指针
    if (cur->lchild == NULL) {//如果左子树为空，把temp赋给左子树
        cur -> lchild = temp;
        temp = cur;//temp存储此时的cur
        cur = temp -> lchild;//当前指针指向左子树
    }
    else {//如果右子树为空，把temp赋给右子树
        cur -> rchild = temp;
        temp = cur;
        cur = temp -> rchild;
    }
    cur -> father = temp;//cur的父亲节点为temp
}
//创建根节点函数（最开始用到）
int creatroot() {
    int i = 1 , j ,  k ,tempnum = 0, cmark = 1;
    if (c[1] == '-') { //如果有负号要处理
        cmark = -1 , i = 2 ;
    }
    j = i;
    while(isdigit(c[j]))
        j++;
    j--;
    for(k = 0 ; j >= i ; j-- , k++)
        tempnum += (pow(10 , k)) * (c[j] - '0');
    init(root , cmark * tempnum);//建立根节点
    cur = root;//当前节点赋给根节点
    i += k;
    return i;
}
//输入函数
void input(){
    int i = 0;
    while(ch = getchar()){
        if(ch == ' ' || ch == '\n')//判断跳过函数
            continue;
        else{
            c[i] = ch;
            if(c[i] == '(') st.push(c[i]);
            if(c[i] == ')') st.pop();
            if(st.empty())  return;//栈为空则退出
            i++; len = i;
        }
    }
}
//处理函数
void solve(int i) {
    int mark = 1;//mark用来标记是正数还是负数
    while (i <= len){
        if (c[i] == '-') {//遇到符号则把mark标记为-1
            mark = -1;
            i++;
            continue;
        }
        if (c[i] == ')') {//遇到右括号则cur指向它的父亲节点
            cur = cur -> father;
            i++;
            mark = 1;
            continue;
        }
        if (isdigit(c[i])) {//如果是数字进行产生
            int tempnum = 0 , j , k;
            j = i + 1;
            while(isdigit(c[j])){
                j++;
            }
            j--;
            for(k = 0 ; j >= i ; j-- , k++){
                tempnum += (pow(10 , k)) * (c[j] - '0');//里面有多个数字情况
            }
            createnode(mark * tempnum);
            i += k;
            mark = 1;
            continue;
        }
        if (c[i] == '(') {
            if(c[i+1] == ')')
                createnode(-999999999);
            i++;
            mark = 1;
            continue;
        }
    }
}
//dfs搜索函数路径值函数
void judge(int tempsum, node *cur) {
    temsum += cur->val;
    if (Found)
        return;
    if (tempsum == sum && cur->lchild->val == Min && cur->rchild->val == Min) {//说明找到了该路径
        Found = 1;
    }
    if (cur -> lchild != NULL && cur -> lchild -> val != Min)
        judge(tempsum  , cur -> lchild);//继续向左儿子搜素
    if (cur -> rchild != NULL && cur -> rchild -> val != Min)
        judge(tempsum  , cur -> rchild);//继续像右儿子搜素
}
//栈清空
void clear() {
    while (!st.empty())
        st.pop();
}
//主函数
int main(){
    int i;
    while (~scanf("%d", &sum)) {
        root = new node;
        Found = 0;
        input();
        if(len == 1) { //如果是这种 5 （） 这种情况直接输出
            printf("no\n") ; continue;
        }
        if(len != 1) {
            i = creatroot() , solve(i);//调用函数
        }
        judge(0 , root);//搜索
        if (Found)       printf("yes\n");
        if (Found == 0)  printf("no\n");
        clear();//栈清空
    }
    return 0;
}