UVa 112 – Tree Summing

112 – Tree Summing

Accepted

C++

0.075

0.010

596

21 hours ago

又來一題字串處理，不過跟上一題不同的是，這題一筆測資有可能多行，所以比較麻煩。題目翻譯請點這裡

首先，很容易可以發現題目的表達式實際上就是二元樹的前序走訪，所以我們可以一邊處理輸入一邊遞迴走訪二元樹，並不用實際把樹建造出來。接下來就只是一些細節要注意，像是節點上的值有可能為負數、小心空白等等。網路上有人用到cin.peek()、cin.ignore()等函式，在這題很有用，有興趣可以去了解。

另外，有時候assert()這個函式很好用，括號裡面可以放已知或你確定的條件，當assert()裡面的條件式為false，會跳出例外並立即終止程式，在UVa上的話會顯示「執行時期錯誤」(Runtime error)，而true則不會發生任何事。這樣的好處是，可以加強一道確認的機制，避免一些爛bug，而且我認為有時也能提升程式碼的可讀性唷!

#include <iostream>
#include <cassert>
using namespace std;

int n;
bool existed;



char get_ch()
{
	char ch = cin.get();
	while(ch == ' ' || ch == '\n')
	{
		ch = cin.get();
	}
	return ch;
}


int get_int(char first)
{
	int num = 0, sign;
	char ch;
	
	
	if(first == '-')
	{
		sign = -1;
	}
	else
	{
		sign = 1;
		num = first-'0';
	}
	
	
	ch = get_ch();
	while(ch != '(')
	{
		num = num*10+(ch-'0');
		ch = get_ch();
	}
	return num*sign;
}



bool read(int sum)
{
	int value;
	char ch;
	bool ln = false, rn = false;
	
	
	ch = get_ch();
	if(ch == ')') return true; // this tree is empty
	
	
	value = get_int(ch); // get root
	
							// ate left tree's '('    ( get_int() )
	ln = read(sum+value); // traversal to left tree
	
	assert(get_ch() == '('); // ate right tree's '('
	rn = read(sum+value); // traversal to right tree
	
	if((ln && rn) && sum+value == n) // on the leaf and meet the requirement
	{
		existed = true;
	}
	
	assert(get_ch() == ')'); // ate ')'
	
	return false;
}


int main()
{
	while(cin >> n)
	{
		existed = false;
		
		assert(get_ch() == '(');
		read(0);
		
		
		
		if(existed)
		{
			cout << "yes" << endl;
		}
		else
		{
			cout << "no" << endl;
		}
	}
}