Chinaunix首页 | 论坛 | 博客
  • 博客访问: 862830
  • 博文数量: 156
  • 博客积分: 6553
  • 博客等级: 准将
  • 技术积分: 3965
  • 用 户 组: 普通用户
  • 注册时间: 2010-06-22 18:36
文章存档

2012年(3)

2011年(43)

2010年(110)

分类: C/C++

2010-10-03 16:18:01

功能介绍:通过键盘输入表达式,程序运行得到结果,显示在屏幕上
如:程序运行后,输入3*4 , 应该在屏幕上显示12
 

算法的设计:

本次实验是表达式的求值,用中缀表达式直接求值,需要定义两个栈:对象栈和运算符栈。

当自作向右扫描表达式的每一个符号时,若当前字符是运算对象,则入对象栈;是运算符时,若这个运算符比栈顶运算符高则入栈,继续向后处理,若这个运算符比栈顶运算符低则从对象栈出栈两个运算量,从运算栈出栈一个运算符进行运算,并将其运算结果入对象栈,继续处理当前字符,直到遇到结束符。

由于运算符中有很多的运算符并且优先级不一样,所以需要用一个二维数组来表示优先级,根据不同的运算来选择相应的符号。

代码实现如下:

#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;
}

阅读(3554) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~