数据结构-表达式求值-题解（C语言代码）

解题思路:C语言栈的应用

注意事项:

参考代码:

#include<stdio.h>
#include<stdlib.h>
#define maxsize 100
#define Etype double
#define Stype char

typedef struct {
 Etype* base;
 Etype* top;
 int size;
}data1;    //操作数栈

typedef struct {
 Stype* base;
 Stype* top;
 int size;
}data2;     //运算符栈

int initstack1(data1* s)
{
 s->base = (Etype*)malloc(sizeof(Etype) * maxsize);
 if (!s->base)
 {
  exit(0);
  return 0;
 }
 else
 {
  s->top = s->base;
  s->size = maxsize;
  return 1;
 }
}

int initstack2(data2* s)
{
 s->base = (Stype*)malloc(sizeof(Stype) * maxsize);
 if (!s->base)
 {
  exit(0);
  return 0;
 }
 else
 {
  s->top = s->base;
  s->size = maxsize;
  return 1;
 }
}

int getstack1(data1* s, Etype* x)
{
 if (s->top == s->base)
  return 0;
 else
 {
  *x = *(s->top - 1);
  return 1;
 }
}

int getstack2(data2* s, Stype* x)
{
 if (s->top == s->base)
  return 0;
 else
 {
  *x = *(s->top - 1);
  return 1;
 }
}

int pop1(data1* s, Etype* x)
{
 if (s->top == s->base)
  return 0;
 else
 {
  *x = *--s->top;
  return 1;
 }
}

int pop2(data2* s, Stype* x)
{
 if (s->top == s->base)
  return 0;
 else
 {
  *x = *--s->top;
  return 1;
 }
}

int push1(data1* s, Etype x)
{
 if (s->top - s->base == maxsize)
  return 0;
 else
 {
  *s->top++ = x;
  return 1;
 }
}

int push2(data2* s, Stype x)
{
 if (s->top - s->base == maxsize)
  return 0;
 else
 {
  *s->top++ = x;
  return 1;
 }
}

double fun(double n, double m, char e)
{
 double sum=0;

 switch (e)
 {
 case '+':sum = n + m; break;
 case '-':sum = n - m; break;
 case '*':sum = n * m; break;
 case '/':sum = n / m; break;
 }

 return sum;
}

int empty(data2* s2)
{
 if (s2->top == s2->base)
  return 0;
 else
  return 1;
}

int main()
{
 char s[100], e, ch;
 int k, n;
 double num, x, y, m;
 data1 s1;
 data2 s2;
 initstack1(&s1);
 initstack2(&s2);

 while ((ch = getchar()) != EOF)
 {
  if (ch == '#')
  {
   while (empty(&s2))
   {
    pop2(&s2, &e);
    pop1(&s1, &x);
    pop1(&s1, &y);
    m = fun(y, x, e);
    push1(&s1, m);
   }
   pop1(&s1, &x);
   printf("%d\n", (int)x);
  }

  if (ch != '#')
  {
   k = 0;
   while (ch >= '0' && ch <= '9' || ch == '.')
   {
    s[k++] = ch;
    ch = getchar();
   }

   if (k != 0)
   {
    s[k] = 0;
    num = atof(s);
    push1(&s1, num);
   }

   if (ch == '*' || ch == '/')
   {
    n = getstack2(&s2, &e);
    if (n == 0 || e == '+' || e == '-' || e == '(')
     push2(&s2, ch);
    else if (e == '*' || e == '/')
    {
     do {
      pop2(&s2, &e);
      pop1(&s1, &x);
      pop1(&s1, &y);
      m = fun(y, x, e);
      push1(&s1, m);
      n = getstack2(&s2, &e);
     } while (n && e != '+' && e != '-' && e != '(');

     push2(&s2, ch);
    }
   }

   else if (ch == '+' || ch == '-')
   {
    n = getstack2(&s2, &e);
    if (n == 0 || e == '(')
     push2(&s2, ch);
    else
    {
     while (n != 0 && e != '(')
     {
      pop2(&s2, &e);
      pop1(&s1, &x);
      pop1(&s1, &y);
      m = fun(y, x, e);
      push1(&s1, m);
      n = getstack2(&s2, &e);
     }
     push2(&s2, ch);
    }
   }

   else if (ch == ')')
   {
    pop2(&s2, &e);
    while (e != '(')
    {
     pop1(&s1, &x);
     pop1(&s1, &y);
     m = fun(y, x, e);
     push1(&s1, m);
     pop2(&s2, &e);
    }
   }

   else if (ch == '(')
   {
    push2(&s2, ch);
   }

   if (ch == '#')
   {
    while (empty(&s2))
    {
     pop2(&s2, &e);
     pop1(&s1, &x);
     pop1(&s1, &y);
     m = fun(y, x, e);
     push1(&s1, m);
    }
    pop1(&s1, &x);
    printf("%d\n", (int)x);
   }
  }

 }

 return 0;
}