kuohaopipei.txt

设计算法判断一个算术表达式的圆括号是否正确配对。 (提示： 对表达式进行扫描

设计算法判断一个算术表达式的圆括号是否正确配对。 (提示：
对表达式进行扫描，凡遇到'('就进栈，遇')'就退掉栈顶的'('，表达式被扫描完毕，栈应为空。
解：根据提示，可以设计算法如下：
#include
#include "stack.h"
int PairBracket( char *S)
{
//检查表达式中括号是否配对
int i;
SeqStack T; //定义一个栈
InitStack (&T);
for (i=0; i {
if ( S=='(' ) Push(&T, S); //遇'('时进栈
if ( S==')' ) Pop(&T); //遇')'时出栈
}
return 　StackEmpty(&T); // 由栈空否返回正确配对与否
}


//栈应用实现进制转换
#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 2  //存储空间初始分配量
#define STACK_ADD_SIZE 10    //存储空间分配增量
#define NULL 0

typedef union Selem    //定义共用体
{
    int i;
    char ch;
    float f;
}selem;
#define selem int
class Sqstack            //定义类
{
private:
    selem* top;
    selem* base;
    int stacksize;
public:    
    //返回栈顶元素
    selem getTop()
    {
        return *(top -1);
    }
    //返回栈底元素
    selem getBase()
    {
        return *base;
    }
    //返回栈长
    int getStacksize()
    {
        return stacksize;
    }
    Sqstack(void);          //构造方法
    ~Sqstack(void);         //折构方法
    //构造一个空栈
    friend void initStack(Sqstack* s);
    //插入新栈e为新栈顶元素--压入栈
    friend bool push(Sqstack*s,selem e);
    //出栈，存在e中
    friend bool pop(Sqstack* s,selem *e);
    //判断栈是否为空
    friend bool isEmpty(Sqstack* s);
};

void initStack(Sqstack* s)
{
    s->base = (selem*)malloc(STACK_INIT_SIZE * sizeof(selem));
    if(s->base == NULL)exit(0);
    s->top = s->base;
    s->stacksize = STACK_INIT_SIZE;
    cout <<"栈底地址"<<s->base<<endl;
}

bool push(Sqstack* s,selem e)
{
    if(s->top - s->base >= s->stacksize)   //如果空间已满，追加空间
    {
        s->base = (selem*)realloc(s->base,STACK_ADD_SIZE * sizeof(selem));
        if(s->base == NULL)exit(0);
    //    s->top = s->base + s->stacksize;
        s->stacksize += STACK_ADD_SIZE;
    }
    *s->top++ = e;
    return true;
}
bool pop(Sqstack* s,selem *e)
{
    if(s->top == s->base)return false;  //如果是空栈
    *e = *--s->top;
    cout <<"栈底地址"<<s->base<<endl;
    return true;
}
bool isEmpty(Sqstack* s)
{
    cout <<s->top <<endl;
    cout <<s->base <<endl;
    if(s->top == s->base)return true;
    return false;
}
Sqstack::Sqstack()
{
    cout << "\n";
}
Sqstack::~Sqstack()
{
    cout <<"\n";
}
void conversion()
{
    Sqstack s;
    selem se,num;
    initStack(&s);
    //cin >> num;
    num = 1348;
    while(num)
    {
        push(&s,num % 8);
        num /= 8;
    }
    while(!isEmpty(&s))
    {
        if(pop(&s,&se))
            printf("%d",se);
    }
    
}

void main()
{
    conversion();
    
}

运行后，发现    while(!isEmpty(&s))
    {
        if(pop(&s,&se))
            printf("%d",se);
    }