数据结构栈的运算

时间:2022-05-13 11:06:45

栈在表达式过程中的应用:建立操作数栈和运算符栈。运算符有优先级。规则:

自左至右扫描表达式,凡是遇到操作数一律进操作数栈。

当遇到运算符时,如果它的优先级比运算符栈栈顶元素的优先级高就进栈。反之,取出栈顶运算符和操作数栈栈顶的连续两个操作数进行运算,并将结果存入操作数栈,然后继续比较该运算符与栈顶运算符的优先级。

左括号一律进运算符栈,右括号一律不进运算符栈,取出运算符栈顶运算符和操作数栈顶的两个操作数进行运算,并将结果压入操作数栈,直到取出左括号为止。


#include <stdio.h>

#define MAX 100

struct operand
{
    int data[MAX];
    int top;
};

struct operator_ch
{
    int top;
    char data[MAX];
};


typedef struct operand OPND;
typedef struct operator_ch OPCH;

void init_OPND_stack(OPND *stack)
{
 stack->top = -1;
}

void init_OPCH_stack(OPCH *stack)
{
 stack->top = -1;
}

void is_empty_OPND(OPND *stack)
{
 if(stack->top == -1)
 {
  return -1;
 }

 return 0;
}

void is_empty_OPCH(OPCH *stack)
{
 if(stack->top == -1)
 {
  return -1;
 }

 return 0;
}

int get_OPND_top(OPND *stack)
{
 if(is_empty_OPND(stack) == -1)
 {
  return -1;
 }

 return stack->data[stack->top];
}

int get_OPCH_top(OPCH *stack)
{
 if(is_empty_OPCH(stack) == -1)
 {
  return -1;
 }

 return stack->data[stack->top];
}

int push_OPND(OPND *stack, int num)
{
    stack->data[++(stack->top)] = num;
}

int push_OPCH(OPND *stack, char ch)
{
    stack->data[++(stack->top)] = ch;
}

int pop_OPND(OPND *stack)
{
 if(is_empty_OPND(stack) == -1)
 {
  return -1;
 }
   
 int num = stack->data[stack->top];

 (stack->top)--;

 return num;
}

char pop_OPCH(OPCH *stack)
{
 if(is_empty_OPCH(stack) == -1)
 {
  return -1;
 }
   
 char ch = stack->data[stack->top];

 (stack->top)--;

 return ch;
}

int get_priority(char ch)
{
 if(ch == '+' || ch == '-')
 {
  return 1;
 }

 if(ch == '*' || ch == '/')
 {
  return 2;
 }
}

int compare_priority(char op_ch, char ch)
{
 if(get_priority(op_ch) > get_priority(ch))
 {
  return 1;
 }
 
 return -1;
}

int count(int num1, int num2, char ch)
{
    int result;

 switch(ch)
 {
  case '+':
  {
            result = a + b;
   break;
  }

  case '-':
  {
   result = a - b;
   break;
  }
  
  case '*':
  {
   result = a * b;
   break;
  }
  
  case '-':
  {
   result = a / b;
   break;
  }
 }

 return result;
}

int main()
{
    char ch;
 char op_ch;

 while((ch = getchar()) != '\n')
 {
        if(ch >= '0' && ch <= '9')
  {
            push_stack1();
  }

  if(ch == '+' || ch == '-' || ch == '*' || ch == '/')
  {
   op_ch = pop_stack2();
   if(compare(op_ch,ch) > 0)
   {
    push_stack2(ch);
   }
   else
   {
    count(a,b,op_ch);
   }
  }
 }
 
 return 0;
}