前言

  1. 抽象数据类型(abstract data type, ADT)可以理解为数据类型的进一步抽象,即把数据类型和数据类型上的运算捆绑在一起。
  2. 这几天了解了如何将中缀表达式转换成后缀表达式,做一个总结。(前缀表达式为”波兰”表达式,后缀为”逆波兰”表达式)。
  3. 将((1+2)+(2+3))3 转换成后缀形式 12+23++3
  4. 此刻的心情很复杂,想想很多事没有做或没有能力做,就有点惭愧,但大多数时候还是无法控制自己。
  5. 将之前博客中挖的坑都好好填一填。

栈的数组实现

  1. 先定义栈的几个基本操作实现。STACKinit、STACKempty、pop、push
  2. 可以将其单独存放在一个.h的头文件中,引用时使用“”(“<>“和”“的区别在于,如果使用”<>”会在系统默认的目录里查找头文件;“”会现在自己编写的文件中查找,未找到则去查找系统默认目录中的。)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    typedef int Item;	//定义操作中使用的数为Item

    Item *num; //数字栈
    int count = 0; //栈中数字的个数
    int n; //初始化栈的个数

    void STACKinit(n){
    num = malloc(sizeof(Item *) * n); //初始化数字栈
    }

    int STACKempty(){
    return count;
    }

    Item pop(){ //数字栈的弹出操作
    if(count)
    count--;
    else
    printf("Error:stack empty!");

    return num[count];
    }

    void push(Item t){
    if(count < n)
    num[count++] = t;
    else
    printf("Error:stack full!");
    }

栈的客户调用

  1. 中缀转后缀的思路是定义一个优先级,四则运算中包括了以下几种符号:( ) + - /。定下规则()的优先级为3,/的优先级为2,+-的优先级为1;
  2. 在做练习题的时候,是0至9的运算……后来救苦想很多时间,以为是逻辑上有错误
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include "stack.h" //上文中自定义的头文件

    int n; //将栈需要的容量定义为全局变量
    int yxj(char c){
    if(c == '+' || c == '-')
    return 1;
    else if(c == '*' || c == '/')
    return 2;
    else if(c == '(' || c == ')')
    return 3;
    }
    int cal(char c){
    int t;

    if(c == '+')
    return pop()+pop();
    else if(c == '*')
    return pop()*pop();
    else if(c == '-'){
    t = pop();
    return t - pop();
    }else if(c == '/'){
    t = pop();
    return t / pop();
    }
    }

    int main(){
    char ch[1000], opr[1000];
    int i, j, flag1, flag2, x = 0; //flag1为前一个操作符的优先级,flag2为后一个操作符的优先级
    gets(ch);

    n = strlen(ch);
    STACKinit(n);

    for(i = 0, j = 0; i < n; i++){
    if(ch[i] >= '0' && ch[i] <= '9'){
    //push(ch[i] - '0');
    while(ch[i]>='0' && ch[i]<='9'){
    x = 10 * x + ch[i] - '0';
    i++;
    }
    --i;
    push(x);
    x = 0;
    }else if(ch[i] != ' '){
    if(!j){ //栈空时直接将操作符压入到 符号栈opr中。
    opr[j++] = ch[i];
    }else{
    //if(ch[i] == '(')
    flag1 = yxj(opr[j-1]);
    flag2 = yxj(ch[i]);
    if(flag1 >= flag2 && opr[j-1] != '('){ //若前一个操作符的优先级 大于 第二个操作符的优先级,则进行弹出操作
    push(cal(opr[--j]));
    opr[j++] = ch[i];
    }else{ //否则进行压入操作。
    opr[j++] = ch[i];
    if(ch[i] == ')'){
    j-=2;
    while(opr[j] != '('){
    push(cal(opr[j]));
    j--;
    }
    }
    }
    }
    }
    }
    while(j){ //清空符号栈进行运算
    --j;
    push(cal(opr[j]));
    }

    printf("%d", pop());
    return 0;
    }

留言

⬆︎TOP