栈的应用2- 数据结构

1. 如何用栈做表达式求值，所谓表达式求值就是给一个表达式然后求出他的值。
   为了帮助理解栈，我们题目设置简单一点，表达式里只有运算符和数字，运算符只有乘法和加法，数字都是一位数。
   再给出代码里，precode 函数里判断两个运算a 和 b 的 优先级，如果a 的优先级高则返回1；operate 函数是根据运算符 theta 计算 a 和 b 的值，并返回计算结果; calc 函数是根据运算符栈顶的计算符，计算数字栈顶两个数的结果，并把结果加入到数字栈里，calc 我们放到最后来实现。
   接下来我们来一步步实现表达式求值吧，首先在主函数里定义一个int 类型的 变量 n, 表示输入的表达式长度，然后程序输入n.

#include 
#include 
#include 

#define ERROR 0
#define OK 1

typedef struct Stack {
    int *elements;
    int max_size, top_index;
} Stack;

void init(Stack *s, int length) {
    s->elements = (int *)malloc(sizeof(int) * length);
    s->max_size = length;
    s->top_index = -1;
}

int push(Stack *s, int element) {
    if (s->top_index >= s->max_size - 1) {
        return ERROR;
    }
    s->top_index++;
    s->elements[s->top_index] = element;
    return OK;
}

int pop(Stack *s) {
    if (s->top_index < 0) {
        return ERROR;
    }
    s->top_index--;
    return OK;
}

int top(Stack *s) {
    return s->elements[s->top_index];
}

int empty(Stack *s) {
    if (s->top_index < 0) {
        return 1;
    } else {
        return 0;
    }
}

int precede(char a, char b) {
    if (a == '*' && b == '+') {
        return 1;
    } else {
        return 0;
    }
}

int operate(char theta, int a, int b) {
    if (theta == '+') {
        return a + b;
    } else {
        return a * b;
    }
}
// 这样，除了calc 函数，我们就把表达式求值写完了，
//  最后，我们来把 calc 函数写全，还记得这个函数吗？
// 从数字栈numbers 里d出两个数， 通过运算符栈 operators 的栈顶运算符计算出结果，然后把结果加入带数字栈numbers 里。
// 首先我们定义一个int 类型的变量a, 让其等于数字栈的栈顶元素，然后删除栈顶元素。
// 接下来我们定义一个 int 类型的变量 b, 让其等于数字栈 numbers 的栈顶元素，然后再删除栈顶元素。
// 接下来，我们用运算栈operators 的栈顶运算符计算a 和 b 的结果，这个可以调用operate 函数来计算，我们再把结果加入栈 numbers 里。
// 为了书写方便，我们用一行代码来实现吧，最后别忘记把栈 operatos 的栈顶元素 删除。
  
void calc(Stack *numbers, Stack *operators) {
    int a = top(numbers);
    pop(numbers);
    int b = top(numbers);
    pop(numbers);
    push(numbers, operate(top(operators),a, b ));
    pop(operators);
}

void clear(Stack *s) {
    free(s->elements);
    free(s);
}

int main() {
    int n;
    scanf("%d",&n);
    // 接下来我们定义两个栈 numbers  和 operators,  均分配一个Stack 类型大小的空间，栈numbers 用于存储要进行计算的数字，然后调用初始化函数 init 对它进行初始化； 栈operators  用于存储要进行计算的运算符， 定义好后同样对它进行初始化。第一个参数为栈名，第二个参数为n, 表示栈的总个数。
    //  接下来 我们定义一个字符串指针 buffer , 并分配 n + 1  字符大小的空间， 用来记录输入的表达式， 然后让程序输入表达式。
    // 接下来 我们用 变量i 来循环处理 输入的表达。
   // 首先，我们定义一个 int 类型的变量i, 初始值为 0，然后写一个while 循环， 
   //  条件 i 小于n, 记得写上花括号。
   //  接下来 我们调用 isdigit 函数看看 buffer 的 第i 个 字符是不是数字，如果是数字 我们把它加入到数字栈里。
   // 我们先来写好条件， 为了方便， 我们把 else 语句 也写好吧，稍后再来实现两种条件，记得把 if 和 else  后面的花括号都补全.
   // 如果第 i 个 字符是数字，那么我们调用插入函数 push 把 该数字加入到数字栈 number 里。
   // 提示一下，把char 类型的字符 转成 int 类型的数字，让字符减去‘0’ 即可。 然后加上 i 加上1 ，接这看下一个 字符。
   // 如果当前，字符不是数字，那么它一定是运算符，我们仔细分析下，如果运算符栈 operatos 为空，或者当前字符的优先级比operators 栈顶的运行符优先级高，那么应该把该运算符加入operators 里。
  // 还记得之前给出的判断优先级函数precede, 函数有两个参数，分别表示两个运算 a 和 b, 如果 a 的优先等级高则返回1，否则返回0，这里我们就可以 用函数precede 来判断优先级了。
  // 如果 运算栈 operators 为空，或者当前运算符的优先级高于栈顶的运算符，那么我们就该运算符加入运算符栈 operators 里，然后让 i  加 1
   
    Stack *numbers =  (Stack *)malloc(sizeof(Stack));
    init(numbers, n);
    Stack *operators =  (Stack *)malloc(sizeof(Stack));
    init(operators,n);
    char  *buffer = (char *)malloc(sizeof(char) * (n+1));
    scanf("%s", buffer);
    int i = 0;
    while (i < n) {
        if(isdigit(buffer[i])) {
            push(numbers, buffer[i] - '0');
            i++;
        } else {
            if(empty(operators) || precede(buffer[i], top(operators))) {
                push(operators, buffer[i]);
                i++;
            } else {
		// 9, 如果运算符栈 operators 不为空，而且栈运算符优先级更好，那么我们要做的 *** 作是，
		// 我们应该从数字栈 numbers 里 d出两个元素，用运算符栈栈顶的运算符计算结果，然后把结果加入到numbers 里。这个 *** 作是之前的calc 功能，所以我们可以 用函数来完成 *** 作。注意calc 的参数依次 是 number 和 operators. 接下来我们对应if 条件语句，把else 语句写好，并且在else 语句里 调用 calc 函数。
		
                calc(numbers, operators);
            
            }
        }
    }
    //  这样我们就是把while 循环写完了，接下来我们就思考一个问题，while 循环结束后，是不是就已经把最终结果算出来了呢？
    // 答案当然是不一定， 运算符栈operators 可能不为空，如果不为空则表示还存在没有处理的 *** 作，这里我们也用一个while 循环，如果运算符栈 operators 不为空，那么就用其栈顶运算符进行 *** 作，直到operators 为空为止。
    // 如果运算符栈 operators 不为空，那就从numbers 栈里d出两个数，然后用运算符栈顶的运算符 进行计算，再将结果加入到numbers 栈里，这里我们只要调用 calc 函数进行 *** 作就可以了。
   
    while (!empty(operators)) {
        calc(numbers, operators);
    }
     //  这样我们就把所有的运算符都计算完了，那么最终的计算结果呢 ？
     // 仔细思考下，我们发现最后的结果就是栈numbers 的 栈顶元素。 我们再while 循环后面输出计算结果，然后再输出一个换行。
     
    printf("%d\n",top(numbers));
    // 在程序结束前， 我们还应该释放占用的内存。
    // 在这里我们需要释放数字栈 numbers 和 运算符栈 operators 所占用的内存空间，我们可以通过调用clear  函数来实现。另外，我们还需要释放字符串指针 buffer  指向的内存空间。
    
    clear(numbers);
    clear(operators);
    free(buffer);
    return 0;
}