/* 算法思想：使用数字栈opnum和运算栈optr分别存放数字和运算符，读到数字就入数字栈，读到运算符时做以下判断(只有'+','-','/','*','(',')'共6种运算符)： 因为括号可以层层叠加，造成解析比较困难，算法的主要思想就是遇到右括号就消一对括号，遇到连续两个运算符就对优先级高的运算符做运算，最终达到括号内最多只有两个数字和一个运算符的目的，再做一次简单的取数字和运算符就得到最终结果 (1)'(':入运算符栈，继续读字符(2)+-:若运算符栈栈顶也为'+-' 则弹出两个数栈的数和一个运算符栈的运算符运算后压入数字栈；(3)/*:若运算符栈栈顶也为* /,则弹出两个数栈的数和一个运算符栈的运算符运算后压入数字栈；(4)')':持续弹出两个数栈的数和一个运算符栈的运算符运算后压入数字栈至遇到(为止；注：目前只支持个位数的四则运算
第二版修改
1.将栈的字符变量改为字符串，修改pop函数未释放内存的错误；2.封装几个最小需求函数：从字符串中一次读取一个完整的数字或运算符函数readOp、运算符优先级比较函数compPrior、栈顶优先级等于当前运算符优先级时的脱括号函数delBracket、栈顶优先级大于当前运算符时的退栈并将结果重新压栈的函数priorPop；3.对于“代码能够表达领域规则”，我在compPrior函数中采用二维数组prior[i1][i2]的方式来表示书中的优先级矩阵，以－1、0、1、－9分别表示优先级低、优先级相等、优先级高、优先级错误，这种方式易读性较强，在后续增加新的运算符时也便于修改和理解；
关注：对需求的分析、理解（反映在对需求边界和约束的确定上）、对软件开发活动节奏的把握（反映在功能的实现和演进方式）以及对代码质量的认识（反映在测试的编写以及代码的重构演化上）。*/#include <stdio.h>#include <stdlib.h>
typedef struct Node{ char c; /* 需改成字符串 */ struct Node *next;}Node,*p_Node;typedef struct Stack{ int length; Node *top;}Stack,*p_Stack;void InitStack(p_Stack S){ S->length = 0; S->top = (Node *)malloc(sizeof(Node *)); S->top->next = S->top; S->top->c = '#';}void FreeStack(p_Stack S){ Node *temp = NULL; while(S->top) { if('#' != S->top->c) { temp = S->top; S->top = S->top->next; free(temp); temp = NULL; } else { free(S->top); S->top = NULL; return; } }}void ShowStack(p_Stack S){ Node *temp = S->top; while(temp->c != '#') { printf("%c,", temp->c); temp = temp->next; } printf("%c/n", temp->c); return; } void Push(p_Stack S, char c){ Node * temp = NULL; temp = S->top; S->top = (Node *)malloc(sizeof(Node *)); S->top->next= temp; S->top->c= c;}char GetTop(p_Stack S){ if(S->top) return S->top->c;}char Pop(p_Stack S) { Node *temp = NULL, *to_free = NULL; char c; temp = S->top->next->next; c = S->top->c; to_free = S->top; S->top = S->top->next; /* top指针下移 */ S->top->next = temp; if(to_free) { free(to_free); to_free = NULL; } return c;}Stack opnum, optr; /* 外部变量的数字栈和运算符栈 */int expr(const char *e){ printf("arithmatic expression:/n%s/n/n", e); int opnum1 = 0, opnum2 = 0, result = 0, count = 0; char c = '/0'; while(1) { if(*e >= '0' && *e <= '9') { Push(&opnum, *e++); } else if('(' == *e) /* 输入字符为'('时优先级最低，入运算符栈继续读取 */ { Push(&optr, *e++); } else if('+' == *e || '-' == *e) { if(GetTop(&optr) == '(') /* 优先级大于栈顶元素时压运算符栈 */ { Push(&optr, *e++); } else if(GetTop(&optr) == '+' || GetTop(&optr) == '-' || GetTop(&optr) == '*' || GetTop(&optr) == '/' ) { ShowStack(&opnum); ShowStack(&optr); opnum2 = (int)Pop(&opnum) - 48; opnum1 = (int)Pop(&opnum) - 48; printf("opnum1:%d,opnum2:%d/n", opnum1, opnum2); c = Pop(&optr); if( c == '+') result = opnum1 + opnum2; else if( c == '-') result = opnum1 - opnum2; else if( c == '*') result = opnum1 * opnum2; else if( c == '/') result = opnum1 / opnum2; Push(&opnum, (char)(result + 48)); Push(&optr, *e++); ShowStack(&opnum); ShowStack(&optr); } else if(GetTop(&optr) == '#') { Push(&optr, *e++); } } else if('*' == *e || '/' == *e) { c = *e; if( GetTop(&optr) == '+' || GetTop(&optr) == '-' || GetTop(&optr) == '(' ) /* 优先级大于栈顶元素时入运算符栈 */ { Push(&optr, *e++); } else if( GetTop(&optr) == '*' || GetTop(&optr) == '/' ) { opnum2 = (int)Pop(&opnum) - 48; opnum1 = (int)Pop(&opnum) - 48; if(Pop(&optr) == '*') result = opnum1 * opnum2; else result = opnum1 / opnum2; Push(&opnum, (char)(result + 48)); Push(&optr, *e); e ++; } else if(GetTop(&optr) == '#') { Push(&optr, *e++); } } else if(')' == *e) /* 优先级最高，消括号,每次数栈弹两个，运算符栈弹一个，计算后结果入数栈，继续比较直至遇到'(' */ { while(GetTop(&optr) != '(') { opnum2 = (int)Pop(&opnum) - 48; opnum1 = (int)Pop(&opnum) - 48; c = Pop(&optr); if( c == '+') result = opnum1 + opnum2; else if( c == '-') result = opnum1 - opnum2; else if( c == '*') result = opnum1 * opnum2; else if( c == '/') result = opnum1 / opnum2; Push(&opnum, (char)(result + 48)); } Pop(&optr); /* '('出栈 */ ShowStack(&opnum); ShowStack(&optr); e++; } else if('/0' == *e) { while(GetTop(&optr) != '#') { opnum2 = (int)Pop(&opnum) - 48; opnum1 = (int)Pop(&opnum) - 48; c = Pop(&optr); if( c == '+') result = opnum1 + opnum2; else if( c == '-') result = opnum1 - opnum2; else if( c == '*') result = opnum1 * opnum2; else if( c == '/') result = opnum1 / opnum2; Push(&opnum, (char)(result + 48)); ShowStack(&opnum); ShowStack(&optr); } printf("final result:/n%d/n", result); return result; } else { return -99; } }}
int main(int argc, char *argv[]){ InitStack(&opnum); InitStack(&optr); expr("(1+4-2)*(3+1)+1"); FreeStack(&opnum); FreeStack(&optr); system("PAUSE"); return 0;}
/*版本二，改为字符串，未完*/
#include <stdio.h>#include <stdlib.h>#define STRNUM 10
typedef struct Node{ char *c; /* 需改成字符串 */ struct Node *next;}Node,*p_Node;typedef struct Stack{ Node *top;}Stack,*p_Stack;void InitStack(p_Stack S){ S->top = (Node *)malloc(sizeof(Node *)); S->top->next = S->top; S->top->c = (char *)malloc(STRNUM); memset(S->top->c, '/0', STRNUM); strcpy(S->top->c , "#");}void FreeStack(p_Stack S){ Node *temp = NULL; while(S->top) { if(strcmp("#", S->top->c) != 0) { temp = S->top; S->top = S->top->next; if(temp->c) { free(temp->c); temp->c = ""; } if(temp) { free(temp); temp = NULL; } } else { free(S->top); S->top = NULL; return; } }}void ShowStack(p_Stack S){ Node *temp = S->top; while(strcmp("#", temp->c) != 0) { printf("%s,", temp->c); temp = temp->next; } printf("%s/n", temp->c); return; } void Push(p_Stack S, char *c){ Node * temp = NULL; temp = S->top; S->top = (Node *)malloc(sizeof(Node *)); S->top->next= temp; S->top->c = (char *)malloc(STRNUM); memset(S->top->c, '/0', STRNUM); strcpy(S->top->c, c); /* 段异常 */}char *GetTop(p_Stack S){ if(S->top) return S->top->c;}void Pop(p_Stack S, char *s) { Node *temp = NULL, *to_free = NULL; temp = S->top->next->next; strcpy(s, S->top->c); to_free = S->top; S->top = S->top->next; /* top指针下移 */ S->top->next = temp; if(to_free) { free(to_free); to_free = NULL; }}Stack opnum, optr; /* 外部变量的数字栈和运算符栈 */#if 1int expr(const char *e){ printf("arithmatic expression:/n%s/n/n", e); int opnum1 = 0, opnum2 = 0, result = 0, count = 0; char c = '/0'; char tempstr[STRNUM] = ""; while(1) { if(*e >= '0' && *e <= '9') { Push(&opnum, *e++); } else if('(' == *e) /* 输入字符为'('时优先级最低，入运算符栈继续读取 */ { Push(&optr, *e++); } else if('+' == *e || '-' == *e) { if(GetTop(&optr) == '(' || GetTop(&optr) == '#') /* 优先级大于栈顶元素时压运算符栈 */ { Push(&optr, *e++); } else if(GetTop(&optr) == '+' || GetTop(&optr) == '-' || GetTop(&optr) == '*' || GetTop(&optr) == '/' ) { opnum2 = (int)Pop(&opnum) - 48; opnum1 = (int)Pop(&opnum) - 48; c = Pop(&optr); if( c == '+') result = opnum1 + opnum2; else if( c == '-') result = opnum1 - opnum2; else if( c == '*') result = opnum1 * opnum2; else if( c == '/') result = opnum1 / opnum2; Push(&opnum, (char)(result + 48)); Push(&optr, *e++); } } else if('*' == *e || '/' == *e) { c = *e; if( GetTop(&optr) == '+' || GetTop(&optr) == '-' || GetTop(&optr) == '(' || GetTop(&optr) == '#' ) /* 优先级大于栈顶元素时入运算符栈 */ { Push(&optr, *e++); } else if( GetTop(&optr) == '*' || GetTop(&optr) == '/' ) { opnum2 = (int)Pop(&opnum) - 48; opnum1 = (int)Pop(&opnum) - 48; if(Pop(&optr) == '*') result = opnum1 * opnum2; else result = opnum1 / opnum2; Push(&opnum, (char)(result + 48)); Push(&optr, *e); e ++; } } else if(')' == *e) /* 优先级最高，消括号,每次数栈弹两个，运算符栈弹一个，计算后结果入数栈，继续比较直至遇到'(' */ { while(GetTop(&optr) != '(') { opnum2 = (int)Pop(&opnum) - 48; opnum1 = (int)Pop(&opnum) - 48; c = Pop(&optr); if( c == '+') result = opnum1 + opnum2; else if( c == '-') result = opnum1 - opnum2; else if( c == '*') result = opnum1 * opnum2; else if( c == '/') result = opnum1 / opnum2; Push(&opnum, (char)(result + 48)); } Pop(&optr); /* '('出栈 */ e++; } else if('/0' == *e) { while(GetTop(&optr) != '#') { opnum2 = (int)Pop(&opnum) - 48; opnum1 = (int)Pop(&opnum) - 48; c = Pop(&optr); if( c == '+') result = opnum1 + opnum2; else if( c == '-') result = opnum1 - opnum2; else if( c == '*') result = opnum1 * opnum2; else if( c == '/') result = opnum1 / opnum2; Push(&opnum, (char)(result + 48)); } printf("final result:/n%d/n", result); return result; } else { return -99; } }}#endif
int main(int argc, char *argv[]){ InitStack(&opnum); InitStack(&optr); #if 1 Push(&opnum, "hello"); Push(&opnum, "world"); ShowStack(&opnum); char s[STRNUM] = ""; Pop(&opnum, s); printf("s:%s/n", s); printf("top of opnum:%s/n", GetTop(&opnum)); ShowStack(&opnum); #endif //expr("(1+4-2)*(3+1)+1"); FreeStack(&opnum); FreeStack(&optr); system("PAUSE"); return 0;}
