【数据结构】栈和队列相关例题（C/C++含注释）

一、判断字符串镜像——栈

【问题描述】

试写一个算法，识别依次读入的一个以“@”为结束符的字符序列是否为形如 “序列1&序列2” 模式的字符序列。其中序列1和序列2都不含字符 “&”，且序列2是序列1的逆序列。例如，“ a+b&b+a ”是属该模式的字符序列，而 “1+3&3-1”则不是。

【输入形式】

以@为结尾的一串字符

【输出形式】

若符合模式则输出字符串长度，否则输出no

【样例输入】

a+b&b+a@

【样例输出】

3

【完整代码】

#include 
#include 
#define Stack_Size 1005                   //设栈中元素个数为50
#define StackElementType char
#define FALSE 0
#define TRUE 1

typedef struct
{
    StackElementType elem[Stack_Size];  //用来存放栈中元素的一维数组
    int top;                            //用来存放栈顶元素的下标，top为-1表示空栈
}SeqStack;                              //顺序栈

void InitStack( SeqStack * S )          //初始化
{   /*造一个空栈*/
    S->top = -1;
}

int Push( SeqStack * S, StackElementType x )//进栈
{   /*将x置入S栈新栈顶*/
    if( S->top == Stack_Size-1 ) return FALSE;//栈已满
    S->top++;                           //修改栈顶指针
    S->elem[S->top] = x;                //x进栈
    return TRUE;
}

int Pop( SeqStack * S, StackElementType * x )//出栈
{   /*将S栈顶元素弹出，放到x所指的存储空间中带出*/
    if( S->top == -1 ) return FALSE;    //栈为空
    else
    {
        *x = S->elem[S->top];           //栈顶元素赋给x
        S->top--;                       //修改栈顶指针
        return TRUE;
    }
}

int GetTop( SeqStack * S, StackElementType * x )//读取栈顶元素
{   /*将栈S栈顶元素读出，放到x所指的存储空间中，栈顶指针保持不变*/
    if( S->top == -1 ) return FALSE;    //栈为空
    else
    {
        *x = S->elem[S->top];           //栈顶元素赋给x
        return TRUE;
    }
}

int main()
{
    char temp;
    int ans = 0;
    char * x = (char *)malloc(sizeof(char));
    SeqStack * S = (SeqStack *)malloc(sizeof(SeqStack));
    InitStack(S);
    while( scanf("%c",&temp) ) //压栈，直到'&'停止压栈
    {
        if( temp=='&' ) break;
        Push(S,temp);
    }
    while( scanf("%c",&temp) )
    {
        if( GetTop(S,x) )    //读取栈顶元素且栈不为空
        {
            if( *x==temp )  //如果匹配
            {
                ans++;      //计数+1
                Pop(S,x);   //弹出栈顶元素
                continue;
            }
            else
            {
                printf("no\n");
                return 0;
            }
        }
        else
        {
            if( temp=='@' )
            {
                break;
            }
            else
            {
                printf("no\n");
                return 0;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

二、表达式求值问题

【问题描述】

栈的应用，给定一个以“#”作为结束符的算式，求出算式的结果

【输入形式】

以“#”结尾的表达式，运算数为正整数。每个表达式占一行。

【输出形式】

输出表达式运算的结果。注意分别运用C语言和C++语言如何处理表达式中带小数的数据，输出数据请保留2位小数。

【样例输入】

4+2.53*3-10/5#

3*(7.91-2)#

2.4*3.6/2#

【样例输出】

9.59

17.73

4.32

【完整代码】

#include 
using namespace std;
template 
//构造栈
struct mstack
{
    T a[1000];
    int top;
    //压栈
    void push(T t)
    {
        top++;
        a[top]=t;
    }
    //出栈
    void pop()
    {
        top--;
    }
    //获得栈顶元素
    T gettop()
    {
        return a[top];
    }
};
//判断运算符优先级
/* 运算符优先级表
	'>','>','','>','','>','>','>','','>',
	'>','>','>','>','','>',
	'','>',
	'ch;
            }
            else
                //判断运算符优先级
                switch(Compare(B.gettop(),ch))
                {
                case '>ch;
                    break;
                case '>':
                    double left,right;
                    right=A.gettop();
                    A.pop();
                    left=A.gettop();
                    A.pop();
                    A.push(fun(B.gettop(),left,right));
                    B.pop();
                    break;
                case '=':
                    B.pop();
                    if(ch==')')cin>>ch;
                    break;
                }
            if(B.top==-1)
            {
                cout