[C++知识库]LinuxC应用开发学习笔记（六）--数据结构

栈和队列的应用

主函数（不完整）

#include <stdio.h>
#include <stdlib.h>

#include "sqstack.h"

static void compture(sqstack *snum,datatype* op)
{
    datatype n1,n2,n;
    st_pop(snum,&n2);
    st_pop(snum,&n1);
    switch (*op)
    {
    case '+':
        n = n1+n2;
        break;
    
    case '-':
        n = n1-n2;
        break;

    case '*':
        n = n1*n2;
        break;

    case '/':
        n = n1/n2;
        break;
    default:
        exit(1);
    }
    st_push(snum,&n);
}
static void deal_bracket(sqstack *snum,sqstack *sop)
{
    datatype old_op;
    st_top(sop,&old_op);

    while(old_op != '(')
    {
        st_pop(sop,&old_op);
        compture(snum,&old_op);
        st_pop(sop,&old_op);
    }
    st_pop(sop,&old_op);
}

static int get_pri(int op)
{
    switch (op)
    {
    case '(':
        return 0;
        break;
    case '+':
    case '-':
        return 1;
        break;
    case '*':
    case '/':
        return 2;
        break; 
    default:
        break;
    }
}


static void deal_op(sqstack*snum,sqstack *sop,int op)
{
    datatype old_op;
    if (st_isempty(sop)||op == '(')
    {
        st_push(sop,&op);
        return;
    }
    st_top(sop,&old_op);

    if (get_pri(op)>get_pri(old_op))
    {
        st_push(sop,&op);
        return;
    }
    while(get_pri(op)<=get_pri(old_op))
    {
        st_pop(sop,&old_op);
        compture(snum,&old_op);
        if (st_isempty(sop))
        {
            break;
        }
        st_pop(sop,&old_op);
    }
    st_push(sop,&op);
    
    

}

int main()
{
    int i;
    char str[] = "(11+3)*2-5";
    datatype old_op;
    int value = 0;
    int flag = 0;
    sqstack *snum,*sop;

    snum = st_create();
    if (snum == NULL)
        {
            exit(1);
        }

    sop = st_create();
        if (sop == NULL)
        {
            exit(1);
        }
    
    while (str[i]!=0)
    {
        if (str[i]>'0'&&str[i]<'9')
        {
            //巧妙处理连续的数字，取数值
            value = value * 10 + (str[i] - '0');
            flag = 1;
        }
        else
        {
            if (flag)
            {
                st_push(snum,&value);
                flag = 0;
                value = 0;
            }
            
            if (str[i]==')')
            {
                deal_bracket(snum,sop);
            }
            else// ( + - * /
            {
                deal_op(snum,sop,str[i]);
            }    
        }
        i++;      
    }   
    if (flag)
        {
            st_push(snum,&value);
        }
    while(!st_isempty(sop))
    {
        st_pop(sop,&old_op);
    }
    st_destory(snum);
    st_destory(sop);
    exit(0);
}