本文共 3915 字,大约阅读时间需要 13 分钟。
刚学完栈的时候写的,主要锻炼下栈的C实现吧!
//栈用单链表来实现#include#include #include #include #include struct Node1{ char a; struct Node1 *next;};struct Node2{ double a; struct Node2 *next;};typedef struct Node1 *Stack1;typedef struct Node2 *Stack2; Stack1 CreakStack1(){ Stack1 S; S = (Stack1)malloc(sizeof(Node1)); S->next = NULL; return S;}Stack2 CreakStack2(){ Stack2 S; S = (Stack2)malloc(sizeof(Node2)); S->next = NULL; return S;}void Push1(char c, Stack1 S){ Stack1 tmp; tmp = (Stack1)malloc(sizeof(Node1)); tmp->a = c; tmp->next = S->next; S->next = tmp;}void Push2(double c, Stack2 S){ Stack2 tmp; tmp = (Stack2)malloc(sizeof(Node1)); tmp->a = c; tmp->next = S->next; S->next = tmp;}void Pop1(Stack1 S){ Stack1 tmp ; tmp = S->next; S->next = tmp->next; free(tmp);}void Pop2(Stack2 S){ Stack2 tmp; tmp = S->next; S->next = tmp->next;}char Top1(Stack1 S){ return(S->next->a);}double Top2(Stack2 S){ return(S->next->a);}bool Isempty1(Stack1 S)//这道题感觉没什么用!反正输入合法!{ return S->next == NULL;}bool Isempty2(Stack2 S){ return S->next == NULL;}char Prior[8][8] ={ // 运算符优先级表 // '+' '-' '*' '/' '(' ')' '#' '^' /*'+'*/'>','>','<','<','<','>','>','<', /*'-'*/'>','>','<','<','<','>','>','<', /*'*'*/'>','>','>','>','<','>','>','<', /*'/'*/'>','>','>','>','<','>','>','<', /*'('*/'<','<','<','<','<','=',' ','<', /*')'*/'>','>','>','>',' ','>','>','>', /*'#'*/'<','<','<','<','<',' ','=','<', /*'^'*/'>','>','>','>','<','>','>','>'}; float Operate(float a, char c, float b){ switch (c) { case '+':return a + b; case'-':return a - b; case'*':return a*b; case'/':return a / b; case'^':return pow(a, b); default:return 0; }}char OP[] = { "+-*/()#^" }; //把可能遇到的8个操作数预先存到一个数组中int In(char a) //判断字符是否为操作数{ int flag = 0; for (int i = 0; i < 8; i++) if (a == OP[i]) { flag = 1; continue; } return flag;}int Ord(char a) //将操作数转化为坐标{ for (int i = 0; i < 8; i++) if (a == OP[i])return i;}char Precede(char a, char b) //返回操作数的优先级{ return(Prior[Ord(a)][Ord(b)]);}float Evaluate(char *Expression){ Stack1 S1 = CreakStack1(); Stack2 S2 = CreakStack2(); Push1('#', S1); char cat[2] = "\0"; char digit[20] = ""; //从表达式数组中接受操作数部分 strcat(Expression, "#"); if (*Expression == '-'); //对第一个数是负数情况的处理;负数只会出现在字符串的第一个或者左括号的下一个哦!!! Push2(0.0, S2); while (!(*Expression == '#'&&Top1(S1) == '#')) { if (!In(*Expression))//操作数 { cat[0] = *Expression; strcat(digit, cat); Expression++; if (In(*Expression)) { double Data = atof(digit); Push2(Data, S2); strcpy(digit, "\0"); } } else //操作符 { if (*Expression == '(') //遇到负数的情况的处理; { if (*++Expression == '-') Push2(0.0, S2); //压入浮点数栈一个0; Expression--; //回到左括号。 } switch (Precede(Top1(S1), *Expression)) { case'<': Push1(*Expression, S1); Expression++; break; case'=': Pop1(S1); Expression++; break; case'>': char c = Top1(S1); Pop1(S1); double a = Top2(S2); Pop2(S2); double b = Top2(S2); Pop2(S2); Push2(Operate(b, c, a), S2); break; }//switch }//else }//while return(Top2(S2));}int main(){ char s[200]; puts("请输入表达式(括号在英文状态下输入)"); scanf("%s", s); puts("该表达式的值为"); printf("%f\n\n", Evaluate(s)); system("pause");}
转载地址:http://akyci.baihongyu.com/