首页 > 代码库 > 栈的总结

栈的总结

一、中缀表达式与后缀表达式

中缀表达式转后缀表达式:
例如: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 }      
View Code

后缀表达式的计算:

技术分享
 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 }
View Code

 二、卡特兰数(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。

 

栈的总结