有一句计算机界中的至理名言:
程序=数据结构+算法
可见数据结构是多么地重要啊......呵呵
今天开始复习了一下数据结构 , 解决了以前的一个问题:
用栈这个数据结构实现四则运算
算法思想是借鉴了<<数据结构(c语言版)>>(清华大学出版社 严蔚敏)中的一些思想 , 最原始的算法就是波兰一位逻辑学家的逆波兰表示法
也就是讲中缀表达式转为后缀表达式的算法 , 感觉很强大 , 呵呵......
好了F话就不多说了 , 直接上代码吧(<^_^>)
算法核心代码:
/*算术表达式求值算法*/
int CountExpression()
{
LinkStack Ope, Num;//操作符栈和操作数栈
char a,b,c,chOpe;
InitStack(&Ope);//初始化符号栈
Push(&Ope, '#');//因为输入中包含# 于是先压一个# 用于判断是否结束
InitStack(&Num);//初始化操作数栈
c = getchar();
//读取遇到#或操作符栈顶为# 就表示结束运算
while(c != '#' || GetTop(&Ope) != '#')
{
//如果是操作数(小于10的一位数) 就压入操作数栈
if(c>= '0' && c<= '9')
{
Push(&Num, c);
c = getchar();
}
//压入操作符栈
else
{
switch(Judge(GetTop(&Ope), c))
{
case '<'://栈顶运算符优先级低于当前操作符, 接收下一个字符
Push(&Ope, c);
c = getchar();
break;
case '='://当遇到右括号时 就出括号, 并接收下一个字符
Pop(&Ope);
c = getchar();
break;
case '>'://栈顶的操作符优先级高 , 说明需要运算 , 并将计算结果压入操作数栈中
chOpe = Pop(&Ope);
a = Pop(&Num);
b = Pop(&Num);
Push(&Num, Operate(b,chOpe,a));
break;
}
}
}
//返回结果 因为链表中的数据域是char型 , 所需要进行char和int之间的转换('0'的对应的ASCII码是48 所以应该减去48)
return GetTop(&Num) - 48;
}
注释应该算是比较清晰了 , 算法就不赘述了
以下是完整代码:
/*
四则运算(栈的应用)
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct stacknode
{
char data;
struct stacknode *next;
}StackNode, *StackNodePtr;
typedef struct
{
StackNodePtr top;
int count;
}LinkStack;
/*初始化*/
void InitStack(LinkStack *S)
{
S->top = NULL;
S->count = 0;
}
/*获取栈顶元素*/
char GetTop(LinkStack *S)
{
if(!(S->top))
return '\0';
return S->top->data;
}
/*压栈*/
void Push(LinkStack *S, char e)
{
StackNodePtr p = (StackNodePtr)malloc(sizeof(StackNode));
p->next = S->top;
p->data = e;
S->top = p;
S->count++;
}
/*出栈*/
char Pop(LinkStack *S)
{
StackNodePtr p;
char data;
if(S->top == NULL)
{
return '\0';
}
p = S->top;
S->top = p->next;
S->count--;
data = p->data;
free(p);
return data;
}
/*选择行列标*/
int ChooseIJ(char index)
{
int i;
switch(index)
{
case '+':
i=0;
break;
case '-':
i=1;
break;
case '*':
i=2;
break;
case '/':
i=3;
break;
case '(':
i=4;
break;
case ')':
i=5;
break;
case '#':
i=6;
}
return i;
}
/*判断运算符优先级*/
char Judge(char top, char ch)
{
static char order[][7]={
// + - * / ( ) #
/* + */ '>','>','<','<','<','>','>',
/* - */ '>','>','<','<','<','>','>',
/* * */ '>','>','>','>','<','>','>',
/* / */ '>','>','>','>','<','>','>',
/* ( */ '<','<','<','<','<','=',' ',
/* ) */ '>','>','>','>',' ','>','>',
/* # */ '<','<','<','<','<',' ','='
};
int i,j;
i = ChooseIJ(top);
j = ChooseIJ(ch);
return order[i][j];
}
/*运算:O1 运算符 O2*/
int Operate(int O1, char op, int O2)
{
int result;
O1 -= 48;
O2 -= 48;
switch(op)
{
case '+':
result = O1 + O2;
break;
case '-':
result = O1 - O2;
break;
case '*':
result = O1 * O2;
break;
case '/':
result = O1 / O2;
break;
}
//输出运算过程
printf("%d %c %d = %d\n", O1, op, O2, result);
return result+48;
}
/*算术表达式求值算法*/
int CountExpression()
{
LinkStack Ope, Num;//操作符栈和操作数栈
char a,b,c,chOpe;
InitStack(&Ope);//初始化符号栈
Push(&Ope, '#');//因为输入中包含# 于是先压一个# 用于判断是否结束
InitStack(&Num);//初始化操作数栈
c = getchar();
//读取遇到#或操作符栈顶为# 就表示结束运算
while(c != '#' || GetTop(&Ope) != '#')
{
//如果是操作数(小于10的一位数) 就压入操作数栈
if(c>= '0' && c<= '9')
{
Push(&Num, c);
c = getchar();
}
//压入操作符栈
else
{
switch(Judge(GetTop(&Ope), c))
{
case '<'://栈顶运算符优先级低于当前操作符, 接收下一个字符
Push(&Ope, c);
c = getchar();
break;
case '='://当遇到右括号时 就出括号, 并接收下一个字符
Pop(&Ope);
c = getchar();
break;
case '>'://栈顶的操作符优先级高 , 说明需要运算 , 并将计算结果压入操作数栈中
chOpe = Pop(&Ope);
a = Pop(&Num);
b = Pop(&Num);
Push(&Num, Operate(b,chOpe,a));
break;
}
}
}
//返回结果 因为链表中的数据域是char型 , 所需要进行char和int之间的转换('0'的对应的ASCII码是48 所以应该减去48)
return GetTop(&Num) - 48;
}
/*测试*/
int main()
{
printf("%d\n", CountExpression());
return 0;
}
运行结果:
如果大家仔细观察 运行结果 , 可以发现:
每一步的运算结果都是小于10的一位整数
没错 , 这个也是算法的局限性 主要是处理数据上的局限性 , 我想了一下 , 要打破这个局限性 , 貌似有点儿难度 , 等以后灵感来了再来吧……
也欢迎各位高手相互讨论算法