数据结构-算术表达式的求解

Question

问题描述：给定一个算术表达式，通过程序求出最后的结果。
基本要求：
1． 从键盘输入要求解的算术表达式；
2． 采用栈结构进行算术表达式的求解过程；
3． 能够判断算术表达式正确与否；
4． 对于错误表达式给出提示；
5． 对于正确的表达式给出最后的结果；
附程序和图加主要思想

Answer 1

#include<stdio.h>
 
#include<stdlib.h>
 
 
 
#define STACK_SIZE 10              //存储空间初始分配量
 
#define STACK_INCREASE 5    //存储空间分配增量
 
 
 
typedef struct {                //寄存运算符
 
      char* base;           //栈底指针
 
      char* top;                  //栈顶指针
 
      int stacksize;        //当前可使用最大容量
 
}OPTR;
 
typedef struct {                //寄存操作数
 
      double* base;
 
      double* top;
 
      int stacksize;
 
}OPND;
 
 
 
int InitStack(OPTR* s);
 
int InitStack(OPND* s);
 
int Push(OPTR* s, char e);
 
int Push(OPND* s, double e);
 
int Pop(OPTR* s, char* e);
 
int Pop(OPND* s, double* e);
 
char Gettop(OPTR* s);
 
double Gettop(OPND* s);
 
int In(char e);
 
char Precede(char a, char b);
 
double Operate(double a, double b, char t);
 
 
 
//主函数
 
int main()
 
{
 
      OPTR optr;
 
      OPND opnd;
 
      OPND temp;    //临时存储数字，构造多位数
 
      char c;            //接收表达式
 
      char y;            //接收脱掉的括号和井号
 
      char theta;       //接收脱出进行运算的运算符
 
      double a, b;  //接收脱出进行运算的操作数
 
      int g = 1;
 
 
 
      while(g)
 
      {
 
             system("cls");
 
                    double x = 0, z = 0;    //多位数转换
 
                    int n = 1;                   //幂
 
                    int error = 0;               //输入格式错误则报错
 
                    InitStack(&optr);
 
                    InitStack(&opnd);
 
                    InitStack(&temp);
 
            
 
                    printf("请输入整数表达式（以#结束）：\n");
 
                    Push(&optr, '#');
 
                    c = getchar();
 
     
 
                    while (c != '#' || Gettop(&optr) != '#')
 
                    {
 
                           if (c == '0') {
 
                                  Push(&opnd, (double)z);
 
                                  c = getchar();
 
                           }
 
                           else
 
                           {
 
                                  while (!In(c))
 
                                  {                                               //将多位数存入临时栈
 
                                         Push(&temp, c - '0');       //字符转数字
 
                                         c = getchar();
 
                                  }
 
                                  while (temp.base != temp.top)
 
                            {                                 //将临时栈中的数重组为多位数
 
                                         Pop(&temp, &x);
 
                                         z = z + x * n;
 
                                         n *= 10;
 
                                  }
 
                                  n = 1;
 
                                  if (z)Push(&opnd, (double)z);//重组后的多位数入栈
 
                                  z = 0;
 
                           }
 
            
 
                           if (In(c))
 
                           {
 
                                  switch (Precede(Gettop(&optr), c))
 
                                  {
 
                                         case '<':
 
                                                Push(&optr, c);
 
                                                c = getchar();
 
                                                break;
 
                   
 
                                         case '=':
 
                                                Pop(&optr, &y);
 
                                                c = getchar();
 
                                                break;
 
                   
 
                                         case '>':
 
                                                Pop(&optr, &theta);
 
                                                Pop(&opnd, &b);
 
                                                Pop(&opnd, &a);
 
                                                Push(&opnd, Operate(a, b, theta));
 
                                                break;
 
                   
 
                                         case '!':
 
                                                printf("输入错误！");
 
                                                error = 1;
 
                                                break;
 
                                  }
 
                           }
 
                           if (error)break;
 
                    }
 
                    if (!error)
 
                           printf("结果为：%.2f\n", Gettop(&opnd));
 
                    system("pause");
 
 
      }
 
            
 
      return 0;
 
}
 
//构造空栈s
 
int InitStack(OPTR* s) {
 
      s->base = (char*)malloc(STACK_SIZE * sizeof(char));
 
      if (!s->base)
 
             exit(0);//存储分配失败
 
      s->top = s->base;
 
      s->stacksize = STACK_SIZE;
 
      return 1;
 
}
 
int InitStack(OPND* s) {
 
      s->base = (double*)malloc(STACK_SIZE * sizeof(double));
 
      if (!s->base)
 
             exit(0);
 
      s->top = s->base;
 
      s->stacksize = STACK_SIZE;
 
      return 1;
 
}
 
//插入元素e为新的栈顶
 
int Push(OPTR* s, char e) {
 
      if (s->top - s->base >= s->stacksize) {//栈满，追加存储空间
 
             s->base = (char*)realloc(s->base,
 
                    (s->stacksize + STACK_INCREASE) * sizeof(char));
 
             if (!s->base)
 
                    exit(0);
 
             s->top = s->base + s->stacksize;
 
             s->stacksize += STACK_INCREASE;
 
      }
 
      *(s->top) = e;
 
      s->top++;
 
}
 
int Push(OPND* s, double e) {
 
      if (s->top - s->base >= s->stacksize) {
 
             s->base = (double*)realloc(s->base,
 
                    (s->stacksize + STACK_INCREASE) * sizeof(double));
 
             if (!s->base)
 
                    exit(0);
 
             s->top = s->base + s->stacksize;
 
             s->stacksize += STACK_INCREASE;
 
      }
 
      *(s->top) = e;
 
      s->top++;
 
}
 
//删除栈顶元素,返回其值
 
int Pop(OPTR* s, char* e) {
 
      if (s->top == s->base)return 0;
 
      s->top--;
 
      *e = *(s->top);
 
      return 1;
 
}
 
int Pop(OPND* s, double* e) {
 
      if (s->top == s->base)return 0;
 
      s->top--;
 
      *e = *(s->top);
 
      return 1;
 
}
 
//判断栈是否为空，不为空则返回栈顶元素e
 
char Gettop(OPTR* s) {
 
      if (s->top == s->base)
 
             return 0;
 
      char* e = s->top;
 
      e--;
 
      return *e;
 
}
 
double Gettop(OPND* s) {
 
      if (s->top == s->base)
 
             return 0;
 
      double* e = s->top;
 
      e--;
 
      return *e;
 
}
 
//判断是否为运算符
 
int In(char e) {
 
      if (e == '+' || e == '-' || e == '*' || e == '/' || e == '(' || e == ')' || e == '#')
 
             return 1;
 
      else return 0;
 
}
 
//判断优先级
 
char Precede(char a, char b) {
 
      if (a == '+')
 
      {
 
             if (b == '*' || b == '/' || b == '(') return '<';
 
             else return '>';
 
      }
 
      else if (a == '-')
 
      {
 
             if (b == '*' || b == '/' || b == '(') return '<';
 
             else return '>';
 
      }
 
      else if (a == '*')
 
      {
 
             if (b == '(')return '<';
 
             else return '>';
 
      }
 
      else if (a == '/')
 
      {
 
             if (b == '(')return '<';
 
             else return '>';
 
      }
 
      else if (a == '(')
 
      {
 
             if (b == ')')return '=';
 
             else if (b == '#') return '!';
 
             else return '<';
 
      }
 
      else if (a == ')')
 
      {
 
             if (b == '(')return '!';
 
             else return '>';
 
 
 
      }
 
      else if (a == '#')
 
      {
 
             if (b == ')')return '!';
             if (b == '#')return '=';
             else return '<';
      }
}
//计算
double Operate(double a, double b, char theta) {
      switch (theta)
      {
      case '+':
             return a + b;
      case '-':
             return 1.0 * a - b;
      case '*':
             return a * b;
      case '/':if (b != 0)
             return 1.0 * a / b;
                    else
             printf("输入错误！");
             exit(0);
 
      }
 
}