数据结构C语言实现系列[3]——关于栈的一些习题

转载 http://blog.csdn.net/dl88250/article/details/1496577

#include <stdio.h>
#include <stdlib.h>
typedef int elemType;
#include "LinkAccess.c"



/* 对由fname所指字符串为文件名的程序文件进行括号配对检查 */
int bracketsCheck(char *fname)
{
    struct sNode *a;        /* 申明一个链栈 */    
    char ch;
    FILE *fp;
    fp = fopen(fname, "r");
    if(!fp){
        printf("File '%s' no found! ", fname);
        exit(1);
    }
    initStack(&a);
    ch = fgetc(fp);        /* 从文件中读取第一个字符到ch */
    while(ch != EOF){
        printf("%c", ch);
        switch(ch){
            case '{':
            case '[':
            case '(':
                push(&a, ch);
                break;
            case '}':
                if(peek(&a) == '{'){
                    pop(&a);
                }else{
                    return 0;
                }
                break;
            case ']':
                if(peek(&a) == '['){
                    pop(&a);
                }else{
                    return 0;
                }
                break;
            case ')':
                if(peek(&a) == '('){
                    pop(&a);
                }else{
                    return 0;
                }
                break;
        }
        ch = fgetc(fp);
    }
    if(emptyStack(&a)){
        return 1;
    }else{
        return 0;
    }
}

int main()
{
    if(bracketsCheck("ABCD.c")){
        printf(" Match! ");
    }else{
        printf(" Miss match! ");
    }
    system("pause");
    return 0;
}

 

 

#include <stdio.h>
#include <stdlib.h>
typedef double elemType;
#include "LinkAccess.c"

/* 计算由str所指向字符串的后缀表达式（逆波兰式）的值 */
double compute(char *str)
{
    struct sNode *s;/* 用s栈存储操作数和中间计算结果，元素类型为double */
    double x, y;            /* x, y用于保存浮点数 */
    int i = 0;                /* i用于扫描后缀表达式 */
    typedef double elemType;
    initStack(&s);
    /* 扫描后缀表达式中的每个字符，并进行相应处理 */
    while(str[i])
    {
        if(str[i] == ' ')
        {            /* 扫描到空格字符不做任何处理 */
            i++;
            continue;
        }
        switch(str[i])
        {
            case '+':
                x = pop(&s) + pop(&s);
                i++;
                break;
            case '-':
                x = pop(&s);        /* 弹出减数 */
                x = pop(&s) - x;
                i++;
                break;
            case '*':
                x = pop(&s) * pop(&s);
                i++;
                break;
            case '/':
                x= pop(&s);        /* 弹出除数 */
                if(x != 0.0)
                {
                    x = pop(&s) / x;
                }
                else
                {
                    printf("除数为0！ ");
                    exit(1);
                }
                i++;
                break;
            default:/* 扫描到的是浮点数字符串，生成对应的浮点数 */
                x = 0;        /* x保存扫描到的整数部分的值 */
                while(str[i] >= 48 && str[i] <= 57)
                {
                    x = x * 10 + str[i] - 48;
                    i++;
                }
                if(str[i] == '.')
                {
                    double j = 10.0;/* j作为相应小数位的权值 */
                    i++;
                    y = 0;
                    while(str[i] >= 48 && str[i] <= 57)
                    {
                        y = y + (str[i] - 48) / j;
                        i++;
                        j *= 10;
                    }
                    x += y;/* 把小数部分合并到整数部分x中 */
                }
        }
        /* 把扫描转换后或进行相应运算后得到的浮点数压入栈s中 */
        push(&s, x);
    }
    /* 若计算结束后栈为空则中止运算 */
    if(emptyStack(&s))
    {
        printf("后缀表达式错误！ ");
        exit(1);
    }
    /* 若栈中只有一个元素，则它就是该后缀表达式的值，否则出错 */
    x = pop(&s);
    if(emptyStack(&s))
    {
        return x;
    }
    else
    {
        printf("后缀表达式错误！ ");
        exit(1);
    }
}

/* 返回运算符op所对应的优先级数值 */
int precedence(char op)
{
    switch(op)
    {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '(':
        case '@':
        default:
            return 0;
    }
}

/* 将s1所指向的中缀表达式转换为s2所指向的后缀表达式 */
char *change(char *s1, char *s2)
{
    struct sNode *r;        /* 栈r用于暂存运算符 */
    int i = 0, j = 0;/* i, j分别用于扫描s1和指示s2串中相应字符的位置 */
    char ch;                /* ch用于暂存扫描s1得到的字符 */

    typedef char elemType;
    initStack(&r);
    push(&r, '@');        /* 给栈底放入'@'字符，它具有最低的优先级0 */
    ch = s1[i];                /* ch初值为s1中的第一个字符 */
    
    /* 依次处理中缀表达式中的每个字符 */
    while(ch != '

 

#include <stdio.h>
#include <stdlib.h>
typedef int elemType;
#include "LinkAccess.c"

void transform(long num, int r);/* 把一个长整型数num转换成一个r进制的数输出 */

int main(int argc, char* argv[])
{
    printf("3425的八进制数为：");
    transform(3425, 8);
    printf("3425的六进制数为：");
    transform(3425, 6);
    printf("3425的四进制数为：");
    transform(3425, 4);
    printf("3425的二进制数为：");
    transform(3425, 2);
    system("pause");
    return 0;
}

void transform(long num, int r)
{
    struct sNode *a;
    
    initStack(&a);
    /* 从低到高求出r进制数的每一位并入栈 */
    while(num != 0){
        int k = num % r;
        push(&a, k);
        num /= r;
    }
    /* 从低到高输出r进制数的每一位 */
    while(!emptyStack(&a)){
        printf("%d", pop(&a));
    }
    printf(" ");

    return;
}

 

 

/*有四个元素a, b, c, d依次进栈，任何时候都可以出栈，请写出所有可能的出栈序列。*/

#include <stdio.h>
#include <stdlib.h>
typedef char elemType;
#include "LinkAccess.c"        /* 关于栈操作的算法 */
#define PUSH 1        
#define POP -1
#define SUM_OP 8    /* 总共需要的操作次数，即总字数的2倍（注意：是偶数） */
int serial[SUM_OP] = {0};        /* 保存出入栈的序列 */
struct sNode *stack;


void arrayCpy(int *to, int *from)
{
    int i;
    for(i = 0; i < SUM_OP; i++){
        *(to+i) = *(from+i);
    }
    return;
}
void out(int *o)
{
    int i;
    char c = 'A';
    for(i = 0; i < SUM_OP; i++){
        /* printf("%d ", o[i]); */
        if(o[i] == 1){
            push(&stack, c);
            ++c;
        }else if(o[i] == -1){
            printf("%c ", pop(&stack));
        }
    }
    printf(" ");
    return;
}

void control(int curSubscript, int curTotalPush, int curTotalPop)
{    
    int i;
    int totalVal = 0;
    int cpySeri[SUM_OP] = {0};
    /* 数组满后输出 */
    if(curSubscript == SUM_OP){
        out(serial);
        return; 
    }
    arrayCpy(cpySeri, serial);        /* 保护当次递归前的现场 */
    /* 估值，用于测试是否能出栈 */
    for(i = 0; i < SUM_OP; i++){
        totalVal += serial[i];
    }
    if((curTotalPush < (SUM_OP / 2)) && (totalVal >= 0)){    
        serial[++curSubscript] = PUSH;
        ++curTotalPush;
        control(curSubscript, curTotalPush, curTotalPop);
        --curSubscript;                    /* 恢复现场 */
        arrayCpy(serial, cpySeri);        /* 恢复现场 */
        --curTotalPush;                    /* 恢复现场 */
        serial[++curSubscript] = POP;    /* 用POP进行下一次递归 */
        ++curTotalPop;
        control(curSubscript, curTotalPush, curTotalPop);
    }
    if((curTotalPop <= (SUM_OP / 2)) && (curTotalPop <= curTotalPush)){
        serial[++curSubscript] = POP;
         ++curTotalPop;
        control(curSubscript, curTotalPush, curTotalPop);
    }
    return;
}

int main()
{
    initStack(&stack);        /* 初始化链栈 */
    serial[0] = PUSH;        /* 第一步必须是进栈 */
    control(0, 1, 0);    
    return 0;
}