题意:
给一个数a和一棵带权树T,判断T根到叶子的若干路径的权和中是否有和a相等的。
分析:
栈用来表达式求值有两种办法,一是将表达式转为后序再求值,二是利用单调符号栈一次扫描。单调符号栈一次扫描法求值时维护单调符号栈(栈中总是优先级低的符号在下,‘(’在栈外优先级最高,栈中优先级最低,‘)’在栈外优先级最低,不可能出现在栈中)。先搞清楚表达式求值的单调符号栈一次扫描法这题就容易了,在这题中用栈模拟树的前序遍历。
代码:
//poj 1145
//sep9
#include <iostream>
#include <stack>
using namespace std;bool isChar(char ch)
{return ch=='('||ch==')'||(ch>='0'&&ch<='9')||ch=='-';
}int main()
{int tot;char ch;while(scanf("%d",&tot)==1){stack<int> nums,states;int cnt=0,cur=0;bool read_enable=true;bool find=false;bool flag=false;while(1){if(read_enable)while((ch=getchar())&&!isChar(ch));if(ch=='('){++cnt;read_enable=true;continue;}if(ch==')'){--cnt;if(!states.empty())++states.top();if(!states.empty()&&states.top()==3){if(flag&&cur==tot) find=true;flag=false;cur-=nums.top();nums.pop();states.pop();if(!states.empty())++states.top();}if(cnt==0)break; read_enable=true;continue;}int neg=1;if(ch=='-'){ch=getchar();neg=-1;} int tmp=0;do{int a=ch-'0';tmp=10*tmp+a; }while((ch=getchar())&&ch>='0'&&ch<='9');tmp*=neg;cur+=tmp;flag=true;nums.push(tmp);states.push(0);if(ch=='(')read_enable=false;elseread_enable=true;}printf("%s\n",find?"yes":"no");}return 0;
}