栈在表达式过程中的应用:建立操作数栈和运算符栈。运算符有优先级。规则:
自左至右扫描表达式,凡是遇到操作数一律进操作数栈。
当遇到运算符时,如果它的优先级比运算符栈栈顶元素的优先级高就进栈。反之,取出栈顶运算符和操作数栈栈顶的连续两个操作数进行运算,并将结果存入操作数栈,然后继续比较该运算符与栈顶运算符的优先级。
左括号一律进运算符栈,右括号一律不进运算符栈,取出运算符栈顶运算符和操作数栈顶的两个操作数进行运算,并将结果压入操作数栈,直到取出左括号为止。
#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;
}