首页 > 代码库 > 栈的总结
栈的总结
一、中缀表达式与后缀表达式
中缀表达式转后缀表达式:
例如:9+(3-1)*3+10/2转化为9 3 1-3 * + 10 2 / +
从左到右,遇到操作数就输出,遇到操作符,遇到左括号直接入栈,否则先判断与栈顶元素的优先级,是右括号或者低于或等于栈顶符号的优先级栈顶元素就出栈,并将当前元素进栈,直到结束。(下面代码都是假设操作数在0~9之间的)
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。
栈的总结
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。