堆栈实现计算器(无需转化为后缀表达式，可直接输入)(C语言)

通过堆栈实现计算器已经有很多成熟的算法了，其中不需要将中缀表达式转化为后缀表达式再输入，而可以直接读取中缀表达式进行计算的算法，我是从百度文库上一个分享中学的，觉得讲的蛮不错，是通过规定和比较优先级顺序来实现的，链接地址是：http://wenku.baidu.com/link?url=czidlt4j-9r2mpnjpfisyzb4hnvljqasixigke_qv-6vrzmjp9syd8nnqn88cpclh1faelmxmlufqphthzt41ej-dk59hmnw3petxs2i6uk点击打开链接

所以在这里我只是讲一下通过c语言实现的一些细节。

首先是如何比较优先级，规定优先级为'(' < '+', '-' < '*', '/', '%' < '^'，每一次都比较当前输入的运算符和当前运算符堆栈栈顶的运算符，如果当前输入的运算符优先级较高，则直接压入栈中，否则的话将当前栈顶运算符弹出进行运算，然后将结果压入运算数堆栈中，并继续和当前栈顶运算符比较，这里需要注意的是循环结束的条件，除了当前输入的运算符的优先级高于当前栈顶运算符时结束循环之外，当运算符栈为空时也应该结束循环(表示之前所有积压的运算符都已经处理了)，并且无论哪种情况结束循环，都将当前输入的运算符压入栈中。

其次是刚开始的时候，栈中还没有运算符需要直接压入，这时候判断是否直接压入的条件就是运算数栈中的运算数数量有没有超过一个，可以用opnd_stack_size这一变量来记录运算数栈中运算数的数量。

然后是括号的实现，首先遇到括号'('就无条件压入栈中 ，然后因为括号就相当于开始了一个新的子算式，是新算式就需要处理刚开始需要直接压入的运算符(参考上一段)，这种要求的实现可以通过优先级进行，因为'('的优先级最低，之后的操作符无论如何都是直接压入。

然后遇到括号')'就相当于是子算式结束了，相当于一个'='，这样的话操作和'='类似('='是直接将积压的所有运算符都处理掉)，')'则是将对应的'('前的所有运算符都处理掉并弹出'('。

最后是输入数的问题，因为我的程序中是在出现运算符时才把之前暂时存储的数压入栈中，然后再来处理运算符，这样一来就需要注意的是用一个变量is_last_num来判断上一个输入的是不是数(因为上一个输入的可能是'(')，只有在上一个输入的是数并且现在输入的是符号时才将数压入栈中，否则不执行压栈操作，避免了多余的压栈操作。

 

#include #include #include #include #include #define opndtype double //操作数堆栈的节点结构 typedef struct node_1{ opndtype val; struct node_1 *pnext; }opnd_node; //操作符堆栈的节点结构 typedef struct node_2{ char op; struct node_2 *pnext; }oprt_node; //操作数堆栈的指针 static opnd_node *opnd_stack = null; //操作符堆栈的指针 static oprt_node *oprt_stack = null; //操作数堆栈的节点个数，初始值为0(没有节点) static int opnd_stack_size = 0; //暂时储存输入的操作数 static char num[100]; //压入操作数 void push_opnd(opndtype opnd){ opnd_node *pnode; pnode = (opnd_node*)malloc(sizeof(opnd_node)); if(pnode == null) perror("malloc fail"); pnode->val = opnd; pnode->pnext = opnd_stack; opnd_stack = pnode; opnd_stack_size++; } //弹出操作数 void pop_opnd(){ opnd_node *pnode; assert(!is_opnd_empty()); pnode = opnd_stack; opnd_stack = opnd_stack->pnext; free(pnode); opnd_stack_size--; } //检查操作数堆栈是否为空 int is_opnd_empty(){ return opnd_stack == null; } //销毁操作数堆栈 void destroy_opnd_stack(){ while(opnd_stack != null) pop_opnd(); } //从操作数堆栈栈顶读取操作数 opndtype get_opnd(){ assert(!is_opnd_empty()); return opnd_stack->val; } //压入操作符 void push_oprt(char oprt){ oprt_node *pnode; pnode = (oprt_node*)malloc(sizeof(oprt_node)); if(pnode == null) perror("malloc fail"); pnode->op = oprt; pnode->pnext = oprt_stack; oprt_stack = pnode; } //弹出操作符 void pop_oprt(){ oprt_node *pnode; assert(!is_oprt_empty()); pnode = oprt_stack; oprt_stack = oprt_stack->pnext; free(pnode); } //检查操作符堆栈是否为空 int is_oprt_empty(){ return oprt_stack == null; } //销毁操作符堆栈 void destroy_oprt_stack(){ while(oprt_stack != null) pop_oprt(); } //从操作符堆栈栈顶读取操作符 char get_oprt(){ assert(!is_oprt_empty()); return oprt_stack->op; } //比较栈顶操作符与当前输入的操作符的优先级 //优先级规定：'(' < '+', '-' < '*', '/' < '^' int priority(char pre, char cur){ switch(pre){ case'(': return 0; case'+': case'-': if(cur == '+'||cur == '-') return 1; else return 0; case'*': case'/': case'%': if(cur == '^'||cur == '(') return 0; else return 1; case'^': if(cur == '(') return 0; else return 1; } } //检查输入的是否为操作符 int is_oprt(char input){ if(input == '+'||input == '-'||input == '*'||input == '/'||input == '%' ||input == '^'||input == '('||input == ')'||input == '=') return 1; else return 0; } //计算一个操作符的运算结果 void get_result(char oprt){ opndtype op_1, op_2, result; op_2 = get_opnd(); pop_opnd(); op_1 = get_opnd(); pop_opnd(); switch(oprt){ case'+': result = op_1 + op_2; break; case'-': result = op_1 - op_2; break; case'*': result = op_1 * op_2; break; case'/': result = op_1 / op_2; break; case'^': result = pow(op_1, op_2); break; case'%': result = fmod(op_1, op_2); } push_opnd(result); } //读取算式进行计算 opndtype calcu(){ char c, pre_oprt, cur_oprt; int is_last_num = 0, i = 0; while(c = getchar()){ if(is_oprt(c)){ //is_last_num为1表明还有操作数已经输入但尚未压入栈中，将数压入操作数堆栈中，并将is_last_num置为0 if(is_last_num){ push_opnd(atof(num)); i = 0; memset(num, 0, sizeof(num)); is_last_num = 0; } //当输入'='时将栈中所有操作符依次进行计算 if(c == '='){ while(!is_oprt_empty()){ pre_oprt = get_oprt(); pop_oprt(); get_result(pre_oprt); } return get_opnd(); } //操作数栈中的数没有达到2个，还不能进行运算，直接将操作符压入栈中并继续输入 if(opnd_stack_size <= 1){ push_oprt(c); continue; } //当输入')'时将栈中'('后所有操作符依次进行计算，并在最后弹出'('，然后继续输入 if(c == ')'){ pre_oprt = get_oprt(); pop_oprt(); while(pre_oprt != '('){ get_result(pre_oprt); pre_oprt = get_oprt(); pop_oprt(); } } //若当前输入的操作符优先级大于现在栈顶操作符则将操作符压入栈中，否则将栈顶操作符弹出进行计算， //并继续比较与新的栈顶操作符的优先级关系，当新的栈顶操作符优先级小于当前输入的操作符， //或操作符栈为空时，循环结束并将当前输入的操作符压入栈中 else{ pre_oprt = get_oprt(); cur_oprt = c; while(priority(pre_oprt, cur_oprt)){ get_result(pre_oprt); pop_oprt(); if(is_oprt_empty()) break; pre_oprt = get_oprt(); } push_oprt(cur_oprt); } } else{ num[i++] = c; //输入了数且尚未压入栈中 ，将is_last_num置为1 is_last_num = 1; } } } int main(){ opndtype ret = calcu(); printf("%lf", ret); }

最后实现的效果是：