车厢调度1357改版

输入车厢数量，a站进站顺序，以及b站出站顺序

输出能否按照b要求的顺序输出，yes或no

输入：

5

1 2 3 4 5

5 4 3 2 1

输出：

yes

//车厢调度问题

int a[10050],b[10050],c[10050];

int n,b=0,t=0;

int you(int x,int j){

   for(int i=j;i<n;i++){

       if(a[i]==x) return i;

   }

   return -1;

}

int main(){

   cin>>n;

   for(int i=0;i<n;i++) cin>>a[i];

   int j=0;

   for(int i=0;i<n;i++){

       cin>>b[i];

       //1、如果栈空，先进栈一辆车

       if(t==b) c[t++]=a[j++];

       //2、如果当前栈顶符合要求，出栈，下一个车厢

       if(c[t-1]==b[i]) t--;

       //否则 查找a栈是否有这个车厢

       else{

           /*如果有，这个车厢及前面所有车厢入栈，再出栈一次

           否则，no 结束*/

           int k=you(b[i],j);

           if(k>=0){

               while(b[i]!=a[j]){

                   c[t++]=a[j++];

               }

               c[t++]=a[j++];t--;

           }

           else{

               cout<<"no";

               return 0;

           }

       }

   }

   cout<<"yes";

   return 0;

}

后缀表达式问题

中缀，前缀，后缀

中缀：正常的数学表达式     1+2  1+3*5   (1-6)*4

前缀：符号在前的数学表达式  +12  +1*35   *-164

后缀：符号在后的数学表达式  12+  135*+   16-4*

中缀转后缀标准版

1+3*(4-5)/6+7

1、根据符号计算顺序加括号

((1+((3*(4-5))/6))+7)

2、从里到外依次去括号

((1+((3*(45-))/6))+7)

((1+((345-*)/6))+7)

((1+(345-*6/))+7)

((1345-*6/+)+7)

(1345-*6/+7+)

1345-*6/+7+

1、输入一个中缀，输出后缀

遇到数字，正常输出

遇到符号，先入栈，后输出

//无括号

char c[10000];

int t=0,b=0;

for(int i=0;i<s.size();i++){

   if(s[i]>='0'&&s[i]<='9') cout<<s[i];

   else{

       while(t!=b&&yxj(c[t-1])>=yxj(s[i])){

           cout<<c[t-1];

           t--;

       }

       c[t++]=s[i];

   }

}

while(t!=b){

   cout<<c[t-1];

   t--;

}

//有括号

char c[10000];

int t=0,b=0;

for(int i=0;i<s.size();i++){

   if(s[i]>='0'&&s[i]<='9') cout<<s[i];

   else if(s[i]=='(') c[t++]=s[i];

   else if(s[i]==')'){

       while(c[t-1]!='('){

           cout<<c[t-1];

           t--;

       }

       t--;

   }

   else{

       while(t!=b&&c[t-1]!='('&&yxj(c[t-1])>=yxj(s[i])){

           cout<<c[t-1];

           t--;

       }

       c[t++]=s[i];

   }

}

while(t!=b){

   cout<<c[t-1];

   t--;

}

优先级处理： string yxj="+-*/";//01 23   [/2处理同级]

2、输入一个后缀，输出计算结果

遇到数字，入栈

遇到符号，出栈两位，计算再入栈

最后输出栈顶即结果

int js(int a,int b,char c){

   switch(c){

       case '+': return b+a;

       case '-': return b-a;

       case '*': return b*a;

       case '/': return b/a;

   }

   return 999999999;

}

int m[1000],t=0,b=0;

for(int i=0;i<s.size();i++){

   if(s[i]>='0'&&s[i]<='9') m[t++]=s[i]-48;

   else{

       int a=m[t-1];t--;

       int b=m[t-1];t--;

       m[t++]=js(a,b,s[i]);

   }

}

cout<<m[t-1];

3、输入一个中缀，输出计算结果

分别创建数字栈，符号栈

遍历中缀表达式，遇到数字，进数字栈

遇到左括号，进符号栈

遇到右括号，符号栈出栈，出栈时，数字栈参与计算，直到左括号为止

遇到符号，通过优先级符号栈出栈，数字栈参与计算

栈顶即结果

课下任务：

1、通过3流程，完成算法结构

2、1331题

#include <stack>    //栈的工具包，容器，严格按照栈的规律进行入栈出栈控制

//创建栈

stack<数据类型> 变量名;

stack<int> s;

//使用栈，调用函数

s.push(5);//数据 5 入栈

s.push(3);

s.push(7);

s.push(4);

cout<<s.top();//输出栈顶元素 4

s.pop();//出栈

s.empty();//判断栈空，栈空返回true，栈不空返回false

while(!s.empty()){

   cout<<s.top();

   s.pop();

}

3、利用stack工具包对今天的代码进行改编