精华内容
下载资源
问答
  • 其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。 比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个...
    题目:输入两个整数序列。其中一个序列表示栈的push顺序,判断另一个序列有没有可能是对应的pop顺序。为了简单起见,我们假设push序列的任意两个整数都是不相等的。
    

    比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。因为可以有如下的push和pop序列:push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,这样得到的pop序列就是4、5、3、2、1。但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

    //判断输入输出是否符合栈的规则
    #include <iostream>
    #include <stack>
    using namespace std;
    bool isstack(int *pushstr,int *popstr,int length)
    {
        
    	if (pushstr==nullptr||popstr==nullptr||length<=0)
    	{
    		return false;
    	}
    	bool ismstack=false;
    	stack<int> stackdata;//辅助栈
    	int *m_nextpush=pushstr;//输入栈中的数据
    	int *m_nextpop=popstr;//输出栈中的数据
    	stackdata.push(*m_nextpush);//给辅助栈一个初值
    	while (m_nextpop-popstr<length)
    	{
    		//判断栈顶元素是否与输出数组中的数相等,不等的话则继续输入
    		while (*m_nextpop!=stackdata.top())
    		{
    			if (m_nextpush-pushstr<length-1)
    			{
    				m_nextpush++;
    				stackdata.push(*m_nextpush);
    			}
    			//输入数组已经全部输入进去
    			else
    			{
    				m_nextpush==nullptr;
    				break;
    			}	
    		}
    		//若与栈顶元素相等,将栈顶元素pop出去,表示已经输出了一个数,输出数组指针+1,指向下一个输出的数,
    		if (*m_nextpop==stackdata.top())
    		{
    			stackdata.pop();
    			m_nextpop++;
    		}
    		else
    		{
    			break;
    		}
    	}
    	//当输出数组中所有的数都已经输出后,辅助栈的为空时则是正确的
    	if (stackdata.empty()&&m_nextpop-popstr==length)
    	{
    		ismstack=true;
    	}
    	return ismstack;
    }
    int main()
    {
    	int m_push[5]={1,2,3,4,5};
    	int m_pop[5]={4,5,3,2,1};
    	bool c=false;
    	c=isstack(m_push,m_pop,5);
    	if (c==true)
    	{
    		cout<<"Yes"<<endl;
    	}
    	else
    	{
    		cout<<"No"<<endl;
    	}
    	return 0;
    }


    展开全文
  • 设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是( )。 A 5 1 2 3 4 B 4 5 1 3 2 C 4 3 1 2 5 D 3 2 1 5 4 分析: A 1234 比5先入 后出但没有逆序 错误 B 123比45先入 后出没有逆序 变成...

    一句话,先入后出必逆序,违反这个规则的都是错误序列。

    例一:
    设一个栈的输入序列是 1,2,3,4,5,则下列序列中,是栈的合法输出序列的是( )。

    A 5 1 2 3 4
    B 4 5 1 3 2
    C 4 3 1 2 5
    D 3 2 1 5 4
    分析:
    A 1234 比5先入 后出但没有逆序 错误
    B 123比45先入 后出没有逆序 变成了132 错误
    C 12先入 后出没有逆序 错误
    D 正确
    D
    例二:
    有六个元素6,5,4,3,2,1的顺序进栈,问下列( )不是合法的出栈序列?
    A 543612

    B453126

    C 346521

    D 234156
    分析:
    C 65比34先入 后出没有逆序 错误
    C

    展开全文
  • 判断一个按从小到大输入栈的序列是否为栈的输出 规则为,在数 n 的后面(n > 2), 后1 ,2,3 ,n-1的排列得是降序 数的排列得是降序 例如进栈的顺序是1234 那么 4 2 3 1 是不可能的 因为 在 4 的后面 1,2,3 这三...

    栈的最鲜明的特征就是
    先进后出
    判断一个按从小到大输入栈的序列是否为栈的输出
    规则为,在数 n 的后面(n > 2), 后1 ,2,3 ,n-1的排列得是降序
    数的排列得是降序
    例如进栈的顺序是1234
    那么 4 2 3 1
    是不可能的 因为 在 4 的后面 1,2,3 这三个数只能 排成 3 2 1
    还如 3 1 2 4 ,也是不对的 ,在3 的后面 1 2 得按降序的来 按 2 1的 顺序来
    如 3 2 1 4,3 2 4 1,3 4 2 1 就是可以的
    这是 栈的基本性质和输出规则

    接着来分析,对所有情况的输出

    按照 升序的方式输入以 1 2 3 为例
    ((输入序列),(栈中序列),(出栈序列))
    1入栈 ((2,3),(1),())
    这时面临 两种情况
    ①1出栈 ((2,3),(),(1))
    ②2入栈((3),(1,2),())
    这时在①上只有入栈的一种情况
    而在②上是有两种情况的
    一是 3 入栈
    一是 2 出栈
    用图来演示全过程
    (有点丑)
    在这里插入图片描述
    下面是算法得出的结果
    在这里插入图片描述
    就像这样 穷举法

    这是一种比较直接的比较笨重的求法

    还知道一种更笨重的方法,就是输出n 个数的所有排列
    然后根据栈的输出规则 来删除不合法的情况

    算法思维来自
    python的函数重载(一)----参数个数
    给定入栈顺序…

    还有一种算法是
    回溯法
    比较难

    贴一个python算法

    #coding=gbk
    
    def stackallput(q,s,qs):# q 为输入队列储存输入序列 S是栈  qs是输出队列用来储存栈的输出
    #用穷举法递归出所有可能输出情况
    	if(qs.lenth() == lens):  #当输出队列满 说明一种情况产生完毕 输出
    		for i in range(lens):
    			print(qs.out(),end = ' ')
    		print()
    	
    	if q.lenth() == 0:#判断输入队列是否为空 为空 进行出栈
    		if s.lenth() != 0:
    			qs.insert(s.pop())
    			stackallput(q,s,qs)#1
    	else:  #输入队列非空
    		if s.lenth() == 0:  #判断栈是否为空  为空入栈 
    			s.push(q.out())
    			stackallput(q,s,qs)#2
    		else:  #非空 
    			qe = q.copy()
    			se = s.copy()
    			qse = qs.copy()
    			se.push(qe.out()) #情况一  入栈操作
    			stackallput(qe,se,qse)#3
    			qs.insert(s.pop()) #情况二  出栈操作
    			stackallput(q,s,qs)#4
    			
    
    class Stack:#列表  模拟栈
    	def __init__(self):  #初始化栈 列表
    		self.lens = []
    		
    	def pop(self):  #以列表 模拟出栈
    		return self.lens.pop()
    	
    	def push(self,value): #模拟入栈
    			self.lens.append(value)
    	
    	def lenth(self):#测量 栈长  作用 判断栈是否为空
    		return len(self.lens)
    	
    	def copy(self): #复制 栈 作用 用复制的栈代替原栈,保留原栈的储存数据
    		s = Stack()
    		s.lens = self.lens[:]
    		return s
    
    class Queue:#列表 模拟队列
    	def __init__(self,lens = 0):#初始化 两种构造情况 一是长度参数 另一个是不带长度参数  
    		self.lens = [None]*lens
    		for i in range(lens):  #按序 创建队列储存数据
    			self.lens[i] = i+1
    		
    	def out(self):#模拟出队
    		return	self.lens.pop(0)		
    	
    	def lenth(self):#测 队列的长度   作用判断 队列是否为空 队列是否为满
    		return len(self.lens)
    		
    	def insert(self,value):# 模拟入队
    			self.lens.append(value)
    		
    	def copy(self):#复制队列   使用复制队列参与递归 保留原队列数据
    		q = Queue(self.lenth())
    		q.lens = self.lens[:]
    		return q
    	
    lens = int(input("输入一个栈的长度:"))		
    q1 = Queue(lens)#输入队列
    s1 = Stack()#栈
    qs = Queue()#输出队列
    stackallput(q1,s1,qs) #穷举递归求栈的所有输出
    
    
    展开全文
  • 初始化共享栈的基本操作:入栈共享栈的基本操作:出栈链栈的实现链栈的基本操作接口链栈的基本操作初始化入栈出栈取栈顶元素几点说明栈的应用键盘输入字符序列的逆置输出数制转换问题描述样例:把十进制数159转换成...

    双向顺序栈

    双向栈在一维数组中的实现
    • 栈的共享中最常见的是两栈的共享。
    • 具体做法是:
      对两栈共享情况来说,将两个栈底分别设在两端,两个栈顶指针top1和top2相对中间位置动态移动,两个栈之间的分界线是不定的。

    在这里插入图片描述

    栈的结构体定义
    Typedef struct
    {
        Elemtype stack[MAXNUM];
        int  lefttop;     /*左栈栈顶位置指示器*/
        int  righttop;  /*右栈栈顶位置指示器*/
    } dupsqstack;
    

    左栈入栈时,栈顶指针加1,右栈入栈时,栈顶指针减1。
    在这里插入图片描述

    识别左右栈
    为了识别左右栈,必须另外设定标志:
    char status;
    status=’L’;  /*左栈*/
    status=’R’;  /*右栈*/
    
    判断栈满
    判断栈满的条件为:
    s->lefttop+1= =s->rigthtop;
    

    在这里插入图片描述

    共享栈的基本操作:初始化
    int initDupStack(dupsqstack *s)
    {
        /*创建两个共享邻接空间的空栈由指针S指出*/
        if ((s=(dupsqstack*)malloc(sizeof(dupsqstack)))
              = =NULL) return FALSE;
        s->lefttop= -1;
        s->righttop=MAXNUM;
        return TRUE;
    } //initDupStack
    

    在这里插入图片描述

    共享栈的基本操作:入栈
    int pushDupStack(dupsqstack *s,char status,Elemtype x)
    {
         /*把数据元素x压入左栈(status=’L’)或右栈(status=’R’)*/
         if(s->lefttop+1= =s->righttop) return FALSE; /*栈满*/   
         if(status=’L’)  s->stack[++s->lefttop]=x; /*左栈进栈*/
         else if(status=’R’)  s->stack[--s->righttop]=x; /*右栈进栈*/
         else return FALSE; /*参数错误*/
         return TRUE;
    } //pushDupStack
    

    在这里插入图片描述

    共享栈的基本操作:出栈
    Elemtype  popDupStack(dupsqstack *s,char status)
    {
         /*从左栈(status=’L’)或右栈(status=’R’)退出栈顶元素*/
         if(status= =’L’)
         { 
             if (s->lefttop<0)   return NULL;  /*左栈为空*/
             else return (s->stack[s->lefttop--]);   /*左栈出栈*/ 
         }
         else if(status= =’R’)
         { 
             if (s->righttop>MAXNUM-1) return NULL;  /*右栈为空*/
             else return (s->stack[s->righttop++]);   /*右栈出栈*/
         }
         else  return NULL;  /*参数错误*/
    } //popDupStack 
    

    链栈的实现

    • 链栈的结点结构和单链表中的结点结构相同,无须重复定义。由于栈只在栈顶作插入和删除操作,因此链栈中不需要头结点,但要注意链栈中指针的方向是从栈顶指向栈底的,这正好和单链表相反。
    • 不存在栈满上溢的情况,是一种特殊的单链表;
    • 链栈是动态存储结构,无需预先分配存储空间,因此节省存储空间;
    • 入栈时,先申请一个结点的存储空间,然后修改栈顶指针;
    • 出栈时,同样也是将栈顶的后继结点作为栈顶。

    简而言是:就是入栈就是头插法,出栈就是删除头结点

    链栈的基本操作接口
    • 只需要对顺序栈的基本操作接口作两处改动,便可作为链栈的基本操作接口。
      • 初始化时不需要maxsize的参数,因为它不需要事先分配空间;
      • 在进入栈操作时不需要顾及栈的空间是否已经被填满。
    链栈的基本操作
    初始化
    void InitStack( Stack &S) 
    {
        // 构造一个空栈S
        S.top = NULL;   // 设栈顶指针的初值为“空”
        S.length = 0;      // 空栈中元素个数为0
    } // InitStack
    
    • 注意:
      • 将头指针置为空,不要忘记初始化相关的长度
    入栈

    在这里插入图片描述

    void Push( Stack &S, SElemType &e) 
    {
        // 在栈顶之上插入元素e为新的栈顶元素。
        p = new LNode;     // 建新的结点
        if( !p ) exit(1);         // 存储分配失败
        p->data = e;
        p->next = S.top;    // 链接到原来的栈顶
        S.top = p;              // 移动栈顶指针
        ++S.length;           // 栈的长度增1
    } // push
    
    • 注意:
      • 链栈的入栈就是的头插法
      • 反是申请了新的内存,就要判定申请的内存是否成功
      • 修改栈顶指针的时候,不要忘记修改栈的长度
    出栈

    在这里插入图片描述

    bool Pop( Stack &S, SElemType &e) 
    {
        // 若栈不空,则删除S的栈顶元素,用e返回其值,并返回TRUE;
        // 否则返回FALSE。
        if( !S.top ) return FALSE; 
        else 
        {
           e = S.top->data;  // 返回栈顶元素
           q = S.top; 
           S.top = S.top->next;   // 修改栈顶指针
           --S.length;   // 栈的长度减1
           delete q;   // 释放被删除的结点空间
           return TRUE;
        } // else
    } // Pop
    
    • 注意:
      • 出栈要判定栈是否为空,进而判定传出去的值是否有意义
    取栈顶元素
    bool GetTop( Stack &S, SElemType &e) 
    {
       //若栈不空,则用e返回S的栈顶元素,
       //并返回TRUE;否则返回FALSE。
       if( !S.top ) return FALSE;
       e = S.top->data;   //返回非空栈中栈顶元素
       return TRUE;
    } // GetTop
    
    • 注意
      • 判定是否为空给,进而判定返回的值是否有意义
      • 取栈顶元素不同于出栈,不改变逻辑结构
    几点说明
    • 链栈不设头结点,没有意义,用不到
    • 链栈的空间都是离散的,都是临时申请的,不会存在栈满的情况
    • 链栈的出栈和入栈就是的插入和删除相关的结点,只需要修改指针就可完成
    • 链栈的优点:
      • 多个栈共享共享存储空间
      • 栈中的元素个数变化大,存储多个栈,链栈是栈的首选存储方式

    栈的应用

    • 键盘输入字符序列逆置输出
    • 数制转换(十转N)
    • 括弧匹配检验
    • 表达式求值
    • 迷宫求解问题
    键盘输入字符序列的逆置输出

    在这里插入图片描述

    typedef char StackEntry;
    void ReverseRead( )
    {  
          STACK S;                //定义一个栈结构S
          char ch;
          InitStack(&S);             //初始化栈
          while ((ch=getchar())!=’\n’)   //从键盘输入字符,直到输入换行符为止
              Push(&S ,ch);            //将输入的每个字符入栈
          while (!StackEmpty(S)) 
          {  //依次退栈并输出退出的字符
              Pop(&S,&ch);
              putchar(ch);
          }
          putchar(‘\n’);
    }
    
    • 分析与总结
      • 完全没想到用getchar和putchar去简化输入和输出,C++中的cin有识别不了空白符,cout有需要拼接
    数制转换
    问题描述
    • 数制转换:十进制数N和其他d进制数的转换是计算机实现计算的基本问题。
    • 其中一个简单算法基于下列原理:
      N = (N div d)×d + N mod d
      其中div为整除运算,mod为求余运算
    • N除d取余:先余为低,后余为高。
    样例:把十进制数159转换成八进制数

    由十进制转换为其他进制的数的规则,可知,求得的余数的顺序为由低位到高位,而输出则是由高位到低位。因此,这正好利用栈的特点,先将求得的余数依次入栈,输出时,再将栈中的数据出栈。

    在这里插入图片描述
    在这里插入图片描述

    void conversion()
    {
        // 对于输出的任意一个非负十进制整数,打印输出与其等值的八进制数
        InitStack(S);   // 构造空栈
        cin >> N;   // 输入一个十进制数
        while( N ) 
        {
           push( S, N % 8 );   // “余数”进栈
           N = N / 8;   // 非零“商”继续运算
        } // while
        while( !StackEmpty) {  // 和“求余”所得相逆的顺序输出八进制的各位数
           Pop( S, e );
           count << e;
        } // while
    } // conversion
    
    • 分析与总结
      • 基本的思路是一致的,都是对余数进行入栈,然后出栈,就是最红的结果
    括弧匹配检验
    问题描述
    • 假设表达式允许有两种括号:圆括号和方括号,其嵌套顺序随意。

      • 假设在表达式中出现下列匹配情况,则为正确的格式。
        ([ ]())或[([ ][ ])]
      • 假设在表达式中出现下列匹配情况,则为不正确的格式。
        [( ])或([( ))或 (()])
      • 结论:检验括号是否匹配的方法可用期待的急迫程度这个概念来描述。
    • 例如,考虑下列括号序列的匹配过程:

               [  (   [   ]  [   ]   )  ]  
               1    2  3  4  5  6  7  8
      

      可见,上述括号的匹配过程正好类似于入栈和出栈的过程。

    • 针对[( ] )、( ( ) ) ) 、([ ]( ) 这三种错误匹配,从期待匹配的角度描述即为:

      • 来的右括弧不是所期待的;
      • 来的是不速之客;
      • 直到结束,也没有到来所期待的。
    • 这三种情况对应到栈的操作即为:

      • 和栈顶的左括弧不相匹配;
      • 栈中并没有左括弧等在那里;
      • 栈中还有左括弧没有等到和它相匹配的右括弧。
    算法设计思想
    • 凡是出现左括弧,则将左括号进栈。
    • 凡是出现右括弧,首先检查栈是否空。如果栈空,则表明该右括弧多余,否则和栈顶元素比较,若相匹配,则左括弧出栈,否则表明不匹配。
    • 表达式检验结束时,若栈空,则表明表达式中匹配正确,否则表明左括弧有余。
    Status matching(string &exp) 
    {
         // str[]中为输入的字符串,
      //利用栈来检查该字符串中的括号是否匹配
        InitStack(S); 
        int i = 1;
        while (i<=length(exp)) //对字符串中的字符逐一扫描
        {
              swith( exp[i]) 
              {
                    case(,[: 
                        Push(S,exp[i]); i++; break; 
                    case):  
                        if (NOT StackEmpty(S) && GetTop(S) = =() 
                        { Pop(S,e); i++; }  
                        else return ERROR; 
                        break; 
                    case]:  
                       if (NOT StackEmpty(S) && GetTop(S) = =[) 
                       { Pop(S,e); i++; }  
                       else return ERROR;  
                       break;
                  }  //switch
            } //while
            if (StackEmpty(S) ) return OK; 
            else return ERROR;
            DestroySTack(S);
    } //matching
    
    • 分析与总结
      • 比我的思路分析的要全面细致一点,分析方法更科学
      • 列出所有的组合可能,然后分为对的,错的
      • 然后找出所有的错的特点
    表达式求值
    问题描述
    • 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。
      • 操作数可以是常数也可以是被说明为变量或常量的标识符;
      • 运算符可以分为算术运算符、关系运算符和逻辑运算符等三类;
      • 基本界限符有左右括弧和表达式结束符等。
    二元表达式的标识方法
    • 对二元表达式可以有三种不同的标识方法:

      • 中缀表达式:运算符放在两个运算对象中间。(简称中缀式)。
      • 后缀表达式:不包含括号,运算符放在两个运算对象的后面,所有的计算按运算符出现的顺序,严格从左向右进行(不再考虑运算符的优先规则)。(简称后缀式或逆波兰式)。
      • 前缀表达式:同后缀式一样,不包括括号,运算符放在两个运算对象的前面。 (简称前缀式或波兰式)。
    • 在计算机中,对二元表达式可以有三种不同的标识方法:

      • 假设 Exp=S1+OP+S2
        • 第一操作数(S1),运算符(OP),第二操作数(S2)
        • 称OP+S1+S2为表达式的前缀表示法
        • 称S1+OP+S2为表达式的中缀表示法
        • 称S1+S2+OP为表达式的后缀表示法
    • 例如:若Exp=a×b + (c-d/e)×f,则它的

      • 前缀式为:+ ×ab ×-c/def
      • 中缀式为:a×b + (c-d/e)×f
      • 后缀式为:ab× cde/-f× +
    算符优先法(中缀式)
    • 根据算术四则运算的规则所确定的运算优先关系的规定来实现对表达式的编译或解释执行的。
    • 一个算术表达式是由操作数(x,y,z,…)和运算符(*,/,+,-,(,),#)组成。
    • 表达式求值必须满足算术四则运算规则:
      • 从左算到右;
      • 先乘除,后加减;
      • 先括号内,后括号外。
    运算符的优先级

    在这里插入图片描述

    运算符间的优先关系规则
    • 遵循算术四则运算规则,一般任意两个相继出现的两个算符θ1和θ2之间的优先关系至多有下面三种之一:
      • θ1<θ2,θ2的优先权高于θ1 ;
      • θ1=θ2,二者优先权相等;
      • θ1>θ2 ,θ2的优先权低于θ1。
    • 一般作为相同运算符,先出现的比后出现的优先级高;先出现的运算符优先级低于(,高于);后出现的运算符优先级高于(,低于);优先权相等的仅有(和)、#。
    • #作为表达式结束符,通常在表达式之前加一#使之成对,当出现“#”=“#”时,表明表达式求值结束,#的优先级最低。
    运算符的优先数
    • 对中缀式中出现的每一个运算符是否即刻进行运算取决于在它后面出现的运算符,如果它的优先数高或等于后面的运算,则它的运算先进行,否则就得等待在它之后出现的所有优先数高于它的运算都完成之后再进行。
    • 进行运算的算符θi是当前扫描过的运算符中优先级最高者,同时,也是到当前最后被保存的运算符,由此可见,可以利用两个栈分别保存扫描过程中遇到的操作数和运算符。
    具体实现
    • 为了实现算符优先算法,可以设定两个工作栈:

      • OPND存放操作数或运算结果,OPTR存放运算符号。
    • 算法思想:

      • 首先置操作数栈OPND为空栈,表达式的起始符#为运算符栈OPTR的栈底元素;
      • 依次读入表达式中的每个字符,
        若运算符是#或栈顶是#,结束计算,返回OPND栈顶值。
        if(是操作数)→则PUSH(OPND,操作数);
        if(是运算符)→则与OPTR栈顶元素进行比较,按优先级(规定详见上表)进行操作;
      • 直到整个表达式求值完毕(当前读入的字符和OPTR栈的栈顶元素均为#)。
    • if栈顶元素<输入运算符,则运算符压入OPTR栈,并接收下一字符;

    • if栈顶元素=运算符但≠‘#’,则脱括号(弹出左括号)并收下一字符;

    • if栈顶元素>运算符,则退栈、按栈顶计算,将结果压入OPND栈。

    • 且该未入栈的运算符要保留,继续与下一个栈顶元素比较!

    样例3*7(7-2)的表达式的求职过程

    在这里插入图片描述

    后缀表达式
    • 由于后缀表达式中没有括号,不需判别优先级,计算严格从左向右进行。故计算一个后缀式要比计算一个中缀式简单的多。

    • 分析中缀式和后缀式两者中运算符出现的次序的不同。

        例一:中缀式为 a×b/c×d-e+f     例二:中缀式为 a+b×c-d/e×f
            后缀式为 ab×c/d×e-f+           后缀式为abc×+de/f×-
      
    • 例一中缀式中运算符出现的先后次序恰为运算的顺序,自然在后缀式中它们出现的次序和原表达式相同。但例二中运算符出现的先后次序不应该是它的运算顺序。按照算术运算规则,先出现的加法应在它之后出现的乘法完成之后进行,并应该在后面出现的减法之前进行;同理,后面一个乘法应后于在它之前出现的除法进行,而先于在它之前的减法进行。

    后缀式的运算规则
    • 运算符在式中出现的顺序恰为表达式的运算顺序。
      • 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。
        • 若将原表达式转换成它的后缀式,那么就可以按后缀式中运算符出现的先后次序来对表达式进行运算了。
      • 可以用两句话来归纳后缀式的求值规则:
        • 先找运算符,后找操作数。
    从中缀表达式得后缀表达式得规则
    • 设立运算符栈;
    • 设表达式的结束符为#,预设运算符栈的栈底为#;
    • 若当前字符是操作数,则直接发送给后缀式;
    • 若当前字符为运算符且优先数大于栈顶运算符,则进栈,否则退出栈顶运算符发送给后缀式;
    • 若当前字符是结束符,则自栈顶至栈底依次将栈中所有运算符发送给后缀式;
    • 若当前字符为界限符(时,总是将它进栈;
    • 若当前字符为界限符)时,将靠近栈顶的第一个左括号(上面的运算符全部依次弹出,发送给后缀式,再丢弃左括号 ( 。
    具体样例A+(B-C/D)XE

    在这里插入图片描述
    在这里插入图片描述

    具体算法
    void transform(char suffix[], char exp[] ) 
    {  // 从合法的表达式字符串 exp 求得其相应的后缀式 suffix  
    	InitStack(S); 
    	Push(S, # );  
    	p = exp; ch = *p;     
    	while (!StackEmpty(S)) {       
            if (!IN(ch, OP)) Pass( suffix, ch); // 直接发送给后缀式    
            else 
           {      
           		switch (ch) 
                {     
                	case(: 
                		Push(S, ch); 
                		break;     
                	case): {      
                		Pop(S, c);      
                		while (c!=()      
                		{ 
                			Pass( suffix, c); 
                			Pop(S, c) } //while  
                			break;}
                	default : { 
                	      while(!Gettop(S, c) && ( precede(c,ch)))      
                	      { 
                             	Pass( suffix, c); 
                             	Pop(S, c); 
                        	} //while        
                        	if ( ch!= ‘#’ ) Push( S, ch);         				break;        
                        	} // case default      
                        } // switch    
                     } // else     
                     if ( ch!= # ) { p++; ch = *p; }
              } // while
         } // transform
                		    														   			     
    
    后缀式得运算过程
    • 对后缀式从左向右扫描,遇见操作数则暂时保存,遇见运算符即可进行运算。
    • 此时参加运算的两个操作数应该是在它之前刚刚碰到的两个操作数,并且先出现的是第一操作数,后出现的是第二操作数。
    • 由此可见:在运算过程中保存操作数的结构应该是个栈。
      在这里插入图片描述
    运用后缀式进行计算
    • 建立一个栈S。
    • 从左向右读后缀式,读到数字就将它转换为数值压入栈中,读到运算符则从栈中依次弹出两个数分别到Y和X,然后以X运算符Y的形式计算出结果,再压入栈S中。
    • 如果后缀式未读完,就重复上面过程,最后输出栈顶的数值为结束。

    在这里插入图片描述

    迷宫求解问题
    问题描述
    • 迷宫求解问题:求迷宫中从入口到出口的所有路径是一个经典的程序设计问题。
    • 在计算机中可以用下页图所示的方块图表示迷宫。
      • 图中的空白方块为通道;
      • 图中的斜线方块为墙;
      • 所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。

    在这里插入图片描述

    算法的基本的思想
    • 探索到出口的路径,具有递归性质:
      • 若当前位置是出口,则问题已解决;
      • 若当前位置不可通,则探索失败;
      • 向可行的方向走一步,从那里出发探索到出口的路径。
    • 本问题的特点:
      • 在每个位置上可能有多个可行选择,有分支,需要逐一试探;
      • 只需要找到一条路经(而不是所有可能路径)。
    • 要解决这个问题,需要:
      • 为问题找一种数据表示;
      • 一种确定可行方向的方式;
      • 防止出现兜圈子的情况(设法纪录已试探过的位置)。

    在这里插入图片描述

    算法的基本的思想(回溯法)
    • 从入口出发,采用试探方法,搜索到目标点(出口)的路径,遇到出口则成功结束。
    • 遇到分支点时选一个方向向前探索,这时需纪录当时的分支点和在这里已试探过的分支(和尚未试探过的分支)。
    • 若遇到死路(所有方向都不能走或已试探过),就退回前一分支点,换一方向再探索。直到找到目标,或者所有可能通路都探索到为止。这类方法称为回溯法。
    • 通过栈来保存分支点的信息
      • 每次回退(回溯)时总是去考虑最近纪录的那个分支点,如果
      • 最近分支点已经没有其它选择,就把它删除;
      • 纪录和删除具有后进先出性质,可以用栈保存分支点信息;
      • 遇到分支点将相关信息压入栈,删除分支点时将它弹出。
    迷宫问题算法框架
    入口点相关信息(位置和方向)入栈;
    While(栈不空){
       取栈顶元素作为当前点和方向(并弹出栈顶)while(当前点还存在未试探的方向){
           求下一点的位置(g,h)if(maze[g][h]是出口){
               输出路径并return}
           if(maze[g][h]==0){ //可前进
              当前点和方向入栈;
              标记maze[g][h]; 
              把(g,h)作为当前点;
           }
       }
    } //while(栈不空); 栈空则说明没有路径存在
    
    

    栈中元素需要纪录走过的位置和已经做过的方向选择。包括三项,分别记录位置的行、列坐标,以及在该位置已选的方向,4个方向编码为0、1、2、3(direction数组的下标值),记录已试探过的方向的最大下标。

    算法使用顺序栈,栈中元素的说明如下:

    struct  NodeMaze
    { 
        int  x,y,d;  //当前位置(x,y)和已试探方向的最大下标d
     } DataType;
    

    所有经过位置都入栈。

    算法伪代码

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 栈的规则是先进后出(输出5,4,3,2,1,),而队列的规则是先进先出(输出还是1,2,3,4,5)。 那么我们如何实现栈和队列的相互转化呢? 1.两个栈表示一个队列 两个栈想要表示一个队列对于一维数组的操作方式,...
  • 采用顺序存储,试编写程序实现将表达式转换成后缀表达式输出。 例如,输入表达式: a+b/c-(d*e+f)*g 输出其后缀表达式:abc/+de*f+g*- 分析: 将表达式转化为后缀表达式思想为:输入表达式,遇到数字或 ...
  • 输入输出】 输入:环总数n。 输出:为尽量体现程序输出结果层次,可以按照从n、n-1、n-2、……、1顺序,将移除掉n号环全部过程作为一个段落输出,然后将移除n-1号环全部过程也作为一个段落输出,其余...
  • 给定一个平衡括号字符串 S,按下述规则计算该字符串分数: () 得 1 分。 AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。 (A) 得 2 * A 分,其中 A 是平衡括号字符串。 示例 1: 输入: “()” 输出: 1 示例 2:...
  • 由中缀式转换成后缀式,同样使用,并运用一些规则来完成。...输入为空后,将元素弹出并输出直到空。 注意,最后生成后缀表达式是考虑了运算符优先级,再配合逆波兰无优先级概念这一性质
  • 算术规则为: k*[encoded_string],表示其中方括号内部 encoded_string 正好重复 k 次。注意 k 保证为正整数。e.g. s = “3*[a2*[c]]”, 返回 “accaccacc” 输入例子1: “3*[a2*[c]]” 输出例子1: “accac
  • 对于路由功能模块学习,也已经很长时间了。关于路由项创建与查找、...对于协议而言,内核中路由功能模块主要就是提供路由查找功能,而查找功能就集合了策略规则、路由项、路由缓存查找,而路由功能模块查找
  • 后缀表达式不包含括号,运算符放在两个运算对象后面,所有计算按运算符出现顺序,严格从左向右进行(不再考虑运算符优先规则,如:(2 + 1) * 3 , 即2 1 + 3 *。利用结构,将后缀表达式结果计算出来。 ...
  • 后缀表达式不包含括号,运算符放在两个运算对象后面,所有计算按运算符出现顺序,严格从左向右进行(不再考虑运算符优先规则,如:(2 + 1) * 3 , 即2 1 + 3 *。利用结构,将后缀表达式结果计算出来。 ...
  • 栈的应用之进制转换

    2016-08-04 21:18:45
    进制转换 ...Time Limit: 1000MS Memory limit: 65536K ...输入一个十进制数N,将它转换成R进制数输出。...输入 ...输入数据包含多个测试实例,每个测试实例包含两...如果R大于10,则对应数字规则参考16进制(比如,10用
  • 给定一个平衡括号字符串 S,按下述规则计算该字符串分数: () 得 1 分。 AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。 (A) 得 2 * A 分,其中 A 是平衡括号字符串。 示例 1: 输入: “()” 输出: 1 示例 2...
  • 牛客网这一题题干如下: 输入描述: 输入包括一个合法括号序列s,s长度length(2 ≤ length ≤ 50),序列中只包含’(‘和’)’。 输出描述: ...4、每个合法括号序列都可以由以上规则生成。 例如:
  • 有效字符串具有如下规则: 任何左括号 ( 必须有相应右括号 )。任何右括号 ) 必须有相应左括号 ( 。左括号 ( 必须在对应右括号之前 )。* 可以被视为单个右括号 ) ,或单个左括号 ( ,或一个空字符串。一个空...
  • 栈的应用之表达式 中缀转后缀表达式 首先,笔者先说下中缀表达式转后缀表达式的规则 遇到字母直接输出 遇到加减乘除首先看栈中有没有运算符,没有的话直接放在栈中,有的话则比较当前元素和栈顶元素的优先级。其实...
  • 后缀表达式不包含括号,运算符放在两个运算对象后面,所有计算按运算符出现顺序,严格从左向右进行(不再考虑运算符优先规则,如:(2 + 1) * 3 , 即2 1 + 3 *。利用结构,将后缀表达式结果计算出来。 ...
  • 后缀表达式不包含括号,运算符放在两个运算对象后面,所有计算按运算符出现顺序,严格从左向右进行(不再考虑运算符优先规则,如:(2 + 3 , 即2 1 + 3 *。利用结构,将后缀表达式结果计算出来。 ...
  • 利用完成后缀表达式计算 1000(ms) 10000(kb) 2114 / 4163后缀表达式不包含括号,运算符放在两个运算对象后面,所有计算按运算符出现顺序,严格从左向右进行(不再考虑运算符优先规则,如:(2 + 1) ...
  • 输入: [2,1,5,6,2,3] 输出: 10 单调分为单调递增和单调递减 1.1 单调递增内元素保持单调递增的栈 1.2 同理单调递减内元素保持单调递减的栈 操作规则(下面都以单调递增为例) 2.1. 如果新...
  • 给定一个平衡括号字符串 S,按下述规则计算该字符串分数:() 得 1 分。AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。(A) 得 2 * A 分,其中 A 是平衡括号字符串。 示例 1:输入: “()” 输出: 1 示例 2:输入...
  • 一种运算受限线性表,遵循后进先出的规则。如下图(图片来自于百度百科) 思路: 计算列表list=[5,3,1,5]能接多少雨水。 1.创建一个stack=[] 2.从左向右遍历列表list,将list元素index,0插入stack中,...
  • ---括号分数

    2018-11-14 15:48:27
    给定一个平衡括号字符串 S,按下述规则计算该字符串分数: 给定一个平衡括号字符串 S,按下述规则计算该字符串分数: () 得 1 分。 AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。 (A) 得 2 * A 分,其中 A...
  • 括号匹配 ...请编写程序判断输入的字符串里左右括号是否全部是匹配,匹配规则即从内到外左括号都与其右边距离最近右括号匹配。如匹配,输出“Yes”,否则,输出“No”。模板类定义如下: ...
  • 后缀表达式不包含括号,运算符放在两个运算对象后面,所有计算按运算符出现顺序,严格从左向右进行(不再考虑运算符优先规则,如:(2 + 1) * 3 , 即2 1 + 3 *。利用结构,将后缀表达式结果计算出来。 ...
  • 给定一个平衡括号字符串 S,按下述规则计算该字符串分数: () 得 1 分。 AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。 (A) 得 2 * A 分,其中 A是平衡括号字符串。 示例 1: 输入: “()” 输出: 1 示例 ...
  • 有效字符串具有如下规则: 任何左括号 ( 必须有相应右括号 )。 任何右括号 ) 必须有相应左括号 ( 。 左括号 ( 必须在对应右括号之前 )。 可以被视为单个右括号 ) ,或单个左括号 ( ,或一个空字符串。 一个空...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 277
精华内容 110
关键字:

栈的输入输出规则