全部博文(156)
分类: C/C++
2010-10-03 16:18:01
算法的设计:
本次实验是表达式的求值,用中缀表达式直接求值,需要定义两个栈:对象栈和运算符栈。
当自作向右扫描表达式的每一个符号时,若当前字符是运算对象,则入对象栈;是运算符时,若这个运算符比栈顶运算符高则入栈,继续向后处理,若这个运算符比栈顶运算符低则从对象栈出栈两个运算量,从运算栈出栈一个运算符进行运算,并将其运算结果入对象栈,继续处理当前字符,直到遇到结束符。
由于运算符中有很多的运算符并且优先级不一样,所以需要用一个二维数组来表示优先级,根据不同的运算来选择相应的符号。
代码实现如下:
#include
#include
typedef int datatype;
typedef struct _node_
{
datatype data;
struct _node_ *next;
} linkstack;
linkstack *CreateEmptyStack_1()
{
linkstack *s;
s = (linkstack *)malloc(sizeof(linkstack));
s->next = NULL;
return s;
}
void CreateEmptyStack_2(linkstack **s)
{
*s = (linkstack *)malloc(sizeof(linkstack));
(*s)->next = NULL;
return;
}
int EmptyStack(linkstack *s)
{
return (NULL == s->next);
}
void ClearStack(linkstack *s)
{
linkstack *p, *q;
p = s->next;
while (p != NULL)
{
q = p;
p = p->next;
free(q);
}
s->next = NULL;
return;
}
void PushStack(linkstack *s, datatype x)
{
linkstack *p;
//printf("x=%d[%c]\n", x, x);
p = (linkstack *)malloc(sizeof(linkstack));
p->data = x;
p->next = s->next;
s->next = p;
return;
}
datatype PopStack(linkstack *s)
{
linkstack *q;
datatype x;
q = s->next;
s->next = q->next;
x = q->data;
free(q);
return x;
}
datatype GetTop(linkstack *s)
{
return s->next->data;
}
int Pri(char op)
{
switch ( op )
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
return 0;
}
int Compute(int op1, int op2, char op)
{
switch ( op )
{
case '+':
return (op1 + op2);
case '-':
return (op1 - op2);
case '*':
return (op1 * op2);
case '/':
return (op1 / op2);
}
return 0;
}
void Deal(linkstack *operator, linkstack *operand, char ch)
{
int op1, op2;
char op;
while (! EmptyStack(operator) && (Pri(ch) <= Pri((char)GetTop(operator))) )
{
op2 = PopStack(operand);
op1 = PopStack(operand);
op = (char)PopStack(operator);
PushStack(operand, Compute(op1, op2, op));
}
PushStack(operator, (int)ch);
return;
}
int main()
{
int sum = 0, op1, op2;
char str[30], *p = str, op;
linkstack *operator, *operand;
operator = CreateEmptyStack_1();
operand = CreateEmptyStack_1();
printf("please input expression : ");
scanf("%s", str);
while (*p != '\0')
{
if ((*p >= '0') && (*p <= '9'))
{
sum = 10*sum + *p - '0';
}
else
{
PushStack(operand, sum);
Deal(operator, operand, *p);
sum = 0;
}
p++;
}
PushStack(operand, sum);
while ( ! EmptyStack(operator) )
{
op2 = PopStack(operand);
op1 = PopStack(operand);
op = (char)PopStack(operator);
PushStack(operand, Compute(op1, op2, op));
}
printf("result = %d\n", GetTop(operand));
return 0;
}