一、中缀表达式与后缀表达式
1 string tosuffix(const string& infix) 2 { 3 string res; 4 stack<int> s; 5 int length=infix.size(); 6 for(int i=0;i<length;i++) 7 { 8 if(infix[i]-‘0‘>=0&&infix[i]-‘9‘<=0) 9 res.push_back(infix[i]); 10 else 11 { 12 if(infix[i]==‘(‘) 13 s.push(infix[i]); 14 //栈顶操作符优先级高于或等于当前操作符则出栈 15 else if(infix[i]==‘+‘||infix[i]==‘-‘) 16 { 17 if(!s.empty()) 18 { 19 //‘(‘优先级最低 20 while(!s.empty()&&s.top()!=‘(‘) 21 { 22 res.push_back(s.top()); 23 s.pop(); 24 } 25 } 26 s.push(infix[i]); 27 } 28 else if(infix[i]==‘*‘||infix[i]==‘/‘) 29 { 30 while(!s.empty()&&(s.top()==‘*‘||s.top()==‘/‘)) 31 { 32 res.push_back(s.top()); 33 s.pop(); 34 } 35 s.push(infix[i]); 36 } 37 else if(infix[i]==‘)‘) 38 { 39 while(s.top()!=‘(‘) 40 { 41 res.push_back(s.top()); 42 s.pop(); 43 } 44 s.pop(); 45 } 46 } 47 } 48 while(!s.empty()) 49 { 50 res.push_back(s.top()); 51 s.pop(); 52 } 53 return res; 54 }
后缀表达式的计算：
1 int suffixtoresult(const string& suffix) 2 { 3 int sum=0; 4 stack<int> st; 5 int length=suffix.size(); 6 int temp; 7 for(int i=0;i<length;i++) 8 { 9 if(suffix[i]-‘0‘>=0&&suffix[i]-‘9‘<=0) 10 { 11 st.push(suffix[i]-‘0‘); 12 } 13 else if(suffix[i]==‘*‘) 14 { 15 temp=st.top(); 16 st.pop(); 17 temp=st.top()*temp; 18 st.pop(); 19 st.push(temp); 20 } 21 else if(suffix[i]==‘/‘) 22 { 23 temp=st.top(); 24 st.pop(); 25 temp=st.top()/temp; 26 st.pop(); 27 st.push(temp); 28 } 29 else if(suffix[i]==‘+‘) 30 { 31 temp=st.top(); 32 st.pop(); 33 temp=st.top()+temp; 34 st.pop(); 35 st.push(temp); 36 } 37 else if(suffix[i]==‘-‘) 38 { 39 temp=st.top(); 40 st.pop(); 41 temp=st.top()-temp; 42 st.pop(); 43 st.push(temp); 44 } 45 } 46 return sum=st.top(); 47 }
二、卡特兰数(Catalan)
问题提出：（买票找零问题）售票开始时没有零钱，每张票50元，有2n个人买票，n个人持50元，n个人持100元，可以让售票不出现找不开零钱的排序多少？(出自编程之美)
问题分析：假设持有50元的人为0，持有100元的人为1，只要满足任意情况下排序从1到2n都是0的个数大于等于1。
问题解决：n个1和n个零的总排序有c(2n,n),n-1个1和n+1个0的排序有c(2n,n-1);
现在我们考虑不合理的情况的排序，当我们出现第一次1的个数超过0的个数的时候就是不合理的，因而只要出现第一次1的个数大于0一个的时候后面出现的任何排序都是不合理的，这时我们可以将后面出现0和1对调，则有n+1个1，所有排序情况为c(2n,n-1)，因而总的合理排序次数为c(2n,n)-c(2n,n-1)可化简为c(2n,n)/(n+1)，这就是卡特兰数的计算公式。
卡特兰数与栈的关系：
假设入栈为0,出栈为1，则要输出合法的栈，所有的序列中一定是0的个数要大于等于1。
卡特兰数可以用于栈在确定的输入序列，计算输出序列的总数。
例如：入栈顺序为123，则出栈有c(2*3,3)/(3+1)=5种序列，分别是123，132，213，231，321。
原文：http://www.cnblogs.com/kiplove/p/6670489.html
