c++STL中Stack

c++stl栈stack的头文件为:

#include <stack>

c++stl栈stack的成员函数介绍

操作 比较和分配堆栈
empty() 堆栈为空则返回真
pop() 移除栈顶元素
push() 在栈顶增加元素
size() 返回栈中元素数目
top() 返回栈顶元素

stack::empty

#include<iostream>  
#include <stack>  
using namespace std;
     int main ()  {  
       stack<int> mystack;    int sum (0);       for (int i=1;i<=10;i++) mystack.push(i);       while (!mystack.empty())    {       sum += mystack.top();       mystack.pop();    }       cout << "total: " << sum << endl;         return 0;  }

stack::push/pop

#include <iostream>  
#include <stack>  
using namespace std;  
   
int main ()  
{  
  stack<int> mystack;  
  int sum (0);  
   
  for (int i=1;i<=10;i++) mystack.push(i);  
   
  while (!mystack.empty())  
  {  
     sum += mystack.top();  
     mystack.pop();  
  }  
   
  cout << "total: " << sum << endl;  
     
  return 0;  
}

实例

判断字符串回文

#include<iostream>
#include<stack>
using namespace std;
bool isMatch(string str)
{
    stack<char> s;
   bool flag=true;
    int i=0;
    while(str[i]!='\0')
    {
        switch(str[i])
        {
        case'(': s.push(str[i]);
        break;
        case'[':s.push(str[i]);
         break;
        case'{':s.push(str[i]);
         break;
        case']':
            if(!s.empty()&&s.top()=='[')
                s.pop();
                else flag=false;
            break;
        case')':
            if(!s.empty()&&s.top()=='(')
                s.pop();
          else flag=false;
            break;
        case '}':
            if(!s.empty()&&s.top()=='{')
                s.pop();
            else flag=false;
            break;
            default:break;
    }
    i++;
        }
    if(!s.empty())
            flag=false;
         return flag;
    }
    int main()
    {
        string s;
        cin>>s;
        bool flag=isMatch(s);
        if(flag) cout<<"yes";
        else cout<<"no";
        return 0;
    }

括号匹配

#include<iostream>
#include<stack>
using namespace std;
bool isMatch(string str)
{
    stack<char> s;
   bool flag=true;
    int i=0;
    while(str[i]!='\0')
    {
        switch(str[i])
        {
        case'(': s.push(str[i]);
        break;
        case'[':s.push(str[i]);
         break;
        case'{':s.push(str[i]);
         break;
        case']':
            if(!s.empty()&&s.top()=='[')
                s.pop();
                else flag=false;
            break;
        case')':
            if(!s.empty()&&s.top()=='(')
                s.pop();
          else flag=false;
            break;
        case '}':
            if(!s.empty()&&s.top()=='{')
                s.pop();
            else flag=false;
            break;
            default:break;
    }
    i++;
        }
    if(!s.empty())
            flag=false;
         return flag;
    }
    int main()
    {
        string s;
        cin>>s;
        bool flag=isMatch(s);
        if(flag) cout<<"yes";
        else cout<<"no";
        return 0;
    }

表达式计算器

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAXSIZE   10
//定义存储整型的栈
typedef struct node
{
    double data[MAXSIZE];
    int top;
} SeqStack;
//定义存储字符型的栈
typedef struct nodeChar
{
    char data[MAXSIZE];
    int top;//栈顶指针
} SeqStackchar;
//创建整型栈
SeqStack *creat_num()
{
    SeqStack *s;
    s = (SeqStack *)malloc(sizeof(SeqStack));
    s->top = -1;
    return s;
}
//创建字符串栈
SeqStackchar *creat_char()
{
    SeqStackchar *s;
    s = (SeqStackchar *)malloc(sizeof(SeqStackchar));
    s->top = -1;
    return  s;
}
int isEmpty(SeqStackchar *s)
{
    if(s->top==-1) return 1;
    else return 0;
}
char GetTop_char(SeqStackchar *s)
{
    if(s->top==-1) exit(1);
    if(s->top!=-1)
        return s->data[s->top];
}
double GetTop_num(SeqStack *s)
{
    if(s->top==-1) exit(1);
    if(s->top!=-1)
        return s->data[s->top];
}
int isOperator(char op)
{
    if(op=='+'||op=='-'||op=='*'||op=='/'||op=='^') return 1;
    else return 0;

}
void push_num(SeqStack *S,double e)
{
    if(MAXSIZE-1==S->top)
    {
        printf("error!\n");
        exit(1);
    }
    //栈顶指向的元素有值
    ++(S->top);
    S->data[S->top]=e;
}
void push_char(SeqStackchar *S,char e)
{
    if(MAXSIZE-1==S->top)
    {
        printf("error\n");
        exit(1);
    }
    //栈顶指向的元素有值
    ++(S->top);
    S->data[S->top]=e;
}
// 出栈
char pop_char(SeqStackchar *S)
{
    char e;
//将栈顶元素出栈，传给e
    if(-1==S->top)
    {
        printf("error！\n");
        exit(1);
    }
    e=S->data[S->top];
    --(S->top);
    return e;
}
double pop_num(SeqStack *S)
{
    double e;
//将栈顶元素出栈，传给e
    if(-1==S->top)
    {
        printf("error！\n");
        exit(0);
    }
    e=S->data[S->top];
    --(S->top);
    return e;
}
int priority(char op)
{
    switch(op)
    {
    case '\0':
        return -1;
    case '(':
        return 0;
    case '+':
    case '-':
        return 1;
    case '*':
    case '/':
    case '^':
        return 2;
    default :
        return -1;
    }
}
double read_number(char str[],int *i)
{
    double x=0.0;
    int k = 0;
    while(str[*i] >='0' && str[*i]<='9')  // 处理整数部分
    {
        x = x*10+(str[*i]-'0');
        (*i)++;
    }

    if(str[*i]=='.') // 处理小数部分
    {
        (*i)++;
        while(str[*i] >= '0'&&str[*i] <='9')
        {
            x = x * 10 + (str[*i]-'0');
            (*i)++;
            k++;
        }
    }
    while(k!=0)
    {
        x /= 10.0;
        k--;
    }
    return x;
}
//   把中缀表达式转换为后缀表达式，返回后缀表达式的长度（包括空格）
void posttoFix(char pre[],char post[],int *n)
{
    int i = 0 ,j=0,q=0;
    SeqStackchar *stack=creat_char();     // 初始化存储操作符的栈
    push_char(stack,'\0');    // 首先把结束标志‘\0’放入栈底
    while(pre[i]!='\0')
    {
        if((pre[i]>='0' && pre[i] <='9')||pre[i] =='.') // 遇到数字和小数点直接写入后缀表达式
        {
            post[j++] = pre[i];
            (*n)++;
        }
        else if(pre[i]=='s')
        {
            i++;
            (*n)++;
            if(pre[i]=='i')
            {
                i++;
                (*n)++;
                if(pre[i]=='n')
                {
                    i++;
                    (*n)++;
                    if(pre[i]=='(')
                    {
                        i++;
                        (*n)++;
                        post[j++]='s';
                        post[j++]='i';
                        post[j++]='n';
                        post[j++]='(';
                        while(pre[i]!=')'&&pre[i]!='\0')
                        {
                            post[j++]=pre[i];
                            i++;
                            (*n)++;
                        }
                        if(pre[i]!=')') {printf("error!\n");exit(1);}
                        post[j++]=')';//为了赋给后面的操作数
                    }
                }
            }
        }
        else if(pre[i]=='c')
        {
            i++;
            (*n)++;
            if(pre[i]=='o')
            {
                i++;
                (*n)++;
                if(pre[i]=='s')
                {
                    i++;
                    (*n)++;
                    if(pre[i]=='(')
                    {           i++;
                            (*n)++;
                        post[j++]='c';
                        post[j++]='o';
                        post[j++]='s';
                        post[j++]='(';
                         while(pre[i]!=')'&&pre[i]!='\0')
                        {

                            post[j++]=pre[i];
                            i++;
                            (*n)++;
                        }      if(pre[i]!=')') {printf("error!\n");exit(1);}
                        post[j++]=')';//为了赋给后面的操作数

                    }
                }
            }
        }
        else if(pre[i]=='t')
        {
            i++;
            (*n)++;
            if(pre[i]=='a')
            {
                i++;
                (*n)++;
                if(pre[i]=='n')
                {
                    i++;
                    (*n)++;
                    if(pre[i]=='(')
                    {     i++;
                        (*n)++;
                        post[j++]='t';
                        post[j++]='a';
                        post[j++]='n';
                        post[j++]='(';
                         while(pre[i]!=')'&&pre[i]!='\0')
                        {

                            post[j++]=pre[i];
                            i++;
                            (*n)++;
                        }      if(pre[i]!=')') {printf("error!\n");exit(1);}
                        post[j++]=')';//为了赋给后面的操作数

                    }
                }
            }
        }
        else if (pre[i]=='(')   // 遇到“（”不用比较直接入栈
            push_char(stack,pre[i]);
        else if(pre[i] ==')')  // 遇到右括号将其对应左括号后的操作符（操作符栈中的）全部写入后缀表达式
        {
            while(GetTop_char(stack)!='(')
            {
                post[j++]=pop_char(stack);
                (*n)++;
            }
            pop_char(stack); // 将“（”出栈，后缀表达式中不含小括号
        }
        else if(isOperator(pre[i]))
        {
            post[j++]=' '; // 用空格分开操作数(
            (*n)++;
            while(priority(pre[i]) <= priority(GetTop_char(stack)))
            {
                // 当前的操作符小于等于栈顶操作符的优先级时，将栈顶操作符写入到后缀表达式，重复此过程
                post[j++] = pop_char(stack);
                (*n)++;
            }
            push_char(stack,pre[i]); // 当前操作符优先级大于栈顶操作符的优先级，将该操作符入栈
        }
        i++;
    }
    while(stack->top!=-1)// 将所有的操作符加入后缀表达式
    {
        post[j++] =pop_char(stack);
        (*n)++;
    }
    post[j]='\0';
}

double Operate(double a,char op,double b)
{
    int i;
    double result=1;
    switch(op)
    {
    case '+':
        result=a+b;
        break;
    case '-':
        result=a-b;
        break;
    case '*':
        result=a*b;
        break;
    case '/':
        result=a/b*1.0;
        break;
    case '^':
        for(i=0; i<b; i++)
            result*=a;
        break;
    default:
        exit(1);
    }
    return result;

}
double postfix_value(char post[])
{
    SeqStack *stack=creat_num();    // 操作数栈
    int i=0,q;
    double temp;
    double result;
    double x1,x2;
    char str[20];
    int k;
    while(post[i] !='\0')
    {
        if(post[i] >='0' && post[i] <='9')
            push_num(stack,read_number(post,&i));
        else if(post[i] == ' ')
            i++;
        else if(post[i]=='s')
        {
            k=0;
            i++;
            if(post[i]=='i')
            {
                i++;
                if(post[i]=='n')
                {
                    i++;
                    if(post[i]=='(')
                    {
                        i++;
                        while(post[i]!=')')
                        {
                            str[k++]=post[i];
                            i++;
                        }
                       i++;
                        str[k]='\0';
                        q=0;
                        result=read_number(str,&q);
                        push_num(stack,sin(result));
                    }
                }
            }
        }
        else if(post[i]=='c')
        {
            k=0;
            i++;
            if(post[i]=='o')
            {
                i++;
                if(post[i]=='s')
                {
                    i++;
                    if(post[i]=='(')
                    {
                        i++;
                        while(post[i]!=')')
                        {
                            str[k++]=post[i];
                            i++;
                        }
                      i++;
                        str[k]='\0';
                        q=0;
                        result=read_number(str,&q);
                        push_num(stack,sin(result));

                    }
                }
            }
        }
        else if(post[i]=='t')
        {
            k=0;
            i++;
            if(post[i]=='a')
            {
                i++;
                if(post[i]=='n')
                {
                    i++;
                    if(post[i]=='(')
                    {
                        i++;
                        while(post[i]!=')')
                        {
                            str[k++]=post[i];
                            i++;
                        }
                         i++;
                        str[k]='\0';
                        q=0;
                        result=read_number(str,&q);
                        push_num(stack,sin(result));
                    }
                }
            }
        }
        else
        {
            x2=pop_num(stack);
            x1=pop_num(stack);
            temp=Operate(x1,post[i],x2);
            push_num(stack,temp);
            i++;
        }
    }
    return GetTop_num(stack);
}
int main()
{
    char exp[100];
    printf("表达式：");
    char post[100] ;
    gets(exp);
    fflush(stdin);
    int i,n=0;           // 返回后缀表达式的长度
    posttoFix(exp,post,&n);
    printf("后缀表达式为：");
    for(i =0 ; post[i]!='\0'; i++)
        printf("%c",post[i]);
    printf("\n由后缀表达式计算出的数值结果:\n");
    printf("%f",postfix_value(post));
    return 0;
}