表达式求解.txt

表达式求值

#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10

typedef struct {  
 char *base;
 char *top;
 int stacksize;
} stack; //字符栈

void InitStack(stack *s) {   
 s->base = (char *)malloc(STACK_INIT_SIZE * sizeof(char));
 if (!s->base) 
 {
  exit(1);
 } 
else 
{
 s->top = s->base;
 s->stacksize = STACK_INIT_SIZE; 
 }
} //初始化栈

char GetTop(stack *s)
{  
 if (s->base == s->top) 
 {
  printf("栈已空\n");
 } 
 else
 { 
 return(*(s->top-1));
 }
} //用e返回栈顶元素

void Pop(stack *s, char *e)
 {  
 if (s->base == s->top)
 {
  printf("栈已空\n");
 }
 else 
{
  *e = *--s->top;
 }
}//返回栈顶元素，注意此处e的值需要改变，因该使用指针

void Push(stack *s, char e)
 {   /
 if (s->top - s->base >= s->stacksize) 
 {
  s->base = (char *)realloc(s->base, (s->stacksize + STACK_INCREMENT) * sizeof(char));
  if (!s->base)
  {
   exit(1);
  } 
  else 
  {
   s->top = s->base + s->stacksize;
   s->stacksize += STACK_INCREMENT;
  }
 } else {
 *s->top++ = e; 
 }
}/将e入栈

char JudgePrecede(char symbol1, char symbol2) {
//优先级判断算法 
 char pre[7][7] = {{'>', '>', '<', '<', '<', '>', '>'},  
                             {'>', '>', '<', '<', '<', '>', '>'},
                             {'>', '>', '>', '>', '<', '>', '>'},
                             {'>', '>', '>', '>', '<', '>', '>'},
                             {'<', '<', '<', '<', '<', '=', ' '},
                             {'>', '>', '>', '>', ' ', '>', '>'},
                             {'<', '<', '<', '<', '<', ' ', '='}
                           } ;
                  
 int row, line;
 
 switch (symbol1) {
  case '+':
   row = 0;
   break;
  case '-':
   row = 1;
   break;
  case '*':
   row = 2;
   break;
  case '/':
   row = 3;
   break;
  case '(':
   row = 4;
   break;
  case ')':
   row = 5;
   break;
  case '#':
   row = 6;
   break; 
  default:
   break;
 }
 
 switch (symbol2) {
  case '+':
   line = 0;
   break;
  case '-':
   line = 1;
   break;
  case '*':
   line = 2;
   break;
  case '/':
   line = 3;
   break;
  case '(':
   line = 4;
   break;
  case ')':
   line = 5;
   break;
  case '#':
   line = 6;
   break; 
  default:
   break;
 }     
 return(pre[row][line]);       
}

int IfOperator(char c) //判断c是否为运算符
 {

 if (c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')' || c == '#') {
  return(1);
 } 
else {
  return(0);
 } 
}

char Operation(char operand1, char Operator, char operand2) //四则运算
{

 switch  (Operator) {
  case '+':
   return(operand1  + operand2 - '0'); 
   break;
  case '-':
   return(operand1 - operand2 + '0');
   break;
  case '*':
   return((operand1 - '0') * (operand2 - '0') + '0');
   break;
  case '/':
   return((operand1 - '0') / (operand2 - '0') + '0');
   break;
  default:
   break;
 }
}

void EvaluateExpression(char *e) 
{
 stack OPND;  
 stack OPTR;
 InitStack(&OPTR);
 InitStack(&OPND);
 Push(&OPTR, '#');
 char  Operator, a, b, c;
 c = getchar();
 while (c != '#' || GetTop(&OPTR) != '#') {
  if (!IfOperator(c)) {
   Push(&OPND, c);
   c = getchar();
  } else {
   switch (JudgePrecede(GetTop(&OPTR), c)) {
    case '<':
     Push(&OPTR, c);
     c = getchar();
     break;
    case '=':
     Pop(&OPTR, &Operator);
     c = getchar();
     break;
    case '>':
     Pop(&OPTR, &Operator);
     Pop(&OPND, &b);
     Pop(&OPND, &a);
     Push(&OPND, Operation(a, Operator, b));
     break;
    default:
     break;
   }
  }
 }
 *e = GetTop(&OPND);
}

void main()
{
 printf("输入一条表达式,以'#'结尾,回车\n");
 char e;
 EvaluateExpression(&e);
 printf("%d\n", e-'0');
 }