一步一步解决表达式计算问题
//链式栈的实际应用-----表达式计算
思考：如果我想要用栈实现下列公式的计算，该怎么办？
(注：这里先不考虑空格问题)
//1+123*5;
char buf[1024];
思考："123"如何转换成整型数123？
答案：
int data = 0;
for(i = 0;i < 3;i++){
data = data * 10 + buf[i] - '\0';
}
思路：
1、创建两个栈
linkstack * operand ;//运算数栈
linkstack * operator; //运算符栈
2、扫描表达式。
<1>若是运算数,合并成一个完整的数data。
规则：直接入操作数栈
push_stack(operator_stack,data);
<2>若是操作符（考虑优先级问题）
规则：1、栈为空，直接入栈
2、当前的运算符号优先级 == 栈顶符合的优先级
直接从运算数栈中取出两个数，再取出栈顶符号。
把计算的结果入运算数栈，然后再把当前的运算符
入符号栈。
（例如：1 + 2 + 4 - 2中，1和2入数据栈，+入符号
栈，比较+和-优先级一样，则计算1+2= 3.
然后结果3入栈，4入栈，+入栈。再次计算）
3、当前的运算符号优先级 >栈顶符合的优先级
不要计算，把当前符号直接再次入栈，此时栈顶元素为
当前符号，然后再把数据入栈，当新的符号来的时候，
比较符号和栈顶元素，若是小于栈顶元素的话，则计算。
（例如：1 + 2 * 3-4,1和2入栈，+入栈，然后判断*和+的
优先级，* > + ,*入栈，3 入栈， 然后判断-和*
的优先级，则- < *,则计算2 和3出栈，*出栈，计算
2 * 3 = 6，然后6入栈，在计算+ 和 -的优先级，一样
则，计算1 + 6 = 7，然后7入栈，4入栈，-入栈，依次计算）
提示：
1、获得优先级函数
int get_level(char operator)
{
switch(operator)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
defalut:
printf("Invalid operator : %c.\n",operator);
return -1;
}
}
2、计算+、-、*、/函数
//参数说明：
//opd 运算数
//opt 运算符
int compute(linkstack *opd,linkstack *opt)
{
int data,data1,data2;
char c = 0;
data2 = pop_stack(opd); //运算数2出栈
data1 = pop_stack(opd);//运算数1出栈
c = pop_stack(opt); //运算符出栈
switch(c)
{
case '+':
data = data1 + data2;
break;
......
}
push_satck(data,opd);//把最后获得的运算数入栈。
}
3、得到最终结果的条件：
当扫描结果的时候，判断运算符栈是否为空，
若是为空则计算，若是不为空，则为空，则
操作数栈中的结果，为我们最后的结果。
4、主函数框架
char buf[1024];
char *p = buf;
int data = 0; //运算数
//输入数据到buf中
while(*p != '\0')
{
//获得运算数
if(*p >= '0' && *p <= '9')
{
data = 0；
//获得运算数
//入运算数栈
continue;
}
if(*p == '+' || *p == '-' .....)
{
//处理运算符
deal_with(operand,operator,*p);
p++;
continue;
}
}
//最后遍历玩表达式,输出运算数栈中的结果，就是我们最终的数据。
//若是用到我们的括号，我们就需要更新代码。
如下图所示：
代码详解：
head.h
#ifndef _HEAD_H_
#define _HEAD_H_
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
//数据元素的类型
typedef int data_t;
//链表的结点类型
typedef struct node
{
data_t data;
struct node *next;
}linknode_t;
//栈头类型
typedef struct
{
//栈顶指针
linknode_t *top;
//栈中元素个数
int n;
}linkstack_t;
extern linkstack_t *create_empty_linkstack();
extern int is_empty_linkstack(linkstack_t *s);
extern int push_linkstack(linkstack_t *s,data_t data);
extern data_t pop_linkstack(linkstack_t *s);
extern data_t get_top_data(linkstack_t *s);
#endif
linkstack.c
#include "head.h"
linkstack_t *create_empty_linkstack()
{
linkstack_t *s = NULL;
s = (linkstack_t *)malloc(sizeof(linkstack_t));
s->top = NULL;
s->n = 0;
return s;
}
int is_empty_linkstack(linkstack_t *s)
{
return s->top == NULL;
}
int push_linkstack(linkstack_t *s,data_t data)
{
linknode_t *temp = NULL;
temp = (linknode_t *)malloc(sizeof(linknode_t));
temp->data = data;
temp->next = s->top;
s->top = temp;
s->n++;
return 0;
}
data_t pop_linkstack(linkstack_t *s)
{
linknode_t *temp = NULL;
data_t data;
temp = s->top;
data = temp->data;
s->top = temp->next;
free(temp);
temp = NULL;
s->n--;
return data;
}
data_t get_top_data(linkstack_t *s)
{
return s->top->data;
}
#if 0
int main()
{
linkstack_t *s = NULL;
int i = 0;
s = create_empty_linkstack();
for(i = 0;i < 10;i++)
{
push_linkstack(s,i);
}
printf("Top data : %d\n",get_top_data(s));
while(!is_empty_linkstack(s))
{
printf("%-5d",pop_linkstack(s));
}
putchar('\n');
return 0;
}
#endif
expression.c
#include "head.h"
int get_priority(char c)
{
switch(c)
{
case '(':
return 0;
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
}
return -1;
}
int compute(linkstack_t *operand,linkstack_t *operator)
{
int data = 0,data1 = 0,data2 = 0;
data2 = pop_linkstack(operand);
data1 = pop_linkstack(operand);
switch(pop_linkstack(operator))
{
case '+':
data = data1 + data2;
break;
case '-':
data = data1 - data2;
break;
case '*':
data = data1 * data2;
break;
case '/':
data = data1 / data2;
break;
}
push_linkstack(operand,data);
return 0;
}
int deal_with(linkstack_t *operand,linkstack_t *operator,char c)
{
int cur_level = 0;
cur_level = get_priority(c);
#if 0
int top_level = 0;
while(1)
{
if(is_empty_linkstack(operator))
{
push_linkstack(operator,c);
return 0;
}
top_level = get_priority(get_top_data(operator));
if(cur_level > top_level)
{
push_linkstack(operator,c);
return 0;
}
compute(operand,operator);
}
#else
/*while(!(is_empty_linkstack(operator) || cur_level > get_priority(get_top_data(operator))))*/
while(1)
{
if(is_empty_linkstack(operator) || cur_level > get_priority(get_top_data(operator)))
{
push_linkstack(operator,c);
return 0;
}
compute(operand,operator);
}
#endif
return 0;
}
int compute_expression(char *p,int *pres)
{
int data = 0;
linkstack_t *operand = NULL;//运算数栈
linkstack_t *operator = NULL;//运算符栈
operand = create_empty_linkstack();
operator = create_empty_linkstack();
/*while(*p != '\0')*/
while(*p)
{
if(*p == ' ')
{
p++;
continue;
}
#if 0
if(*p >= '0' && *p <= '9')
{
push_linkstack(operand,*p - '0');
p++;
continue;
}
#endif
if(*p >= '0' && *p <= '9')
{
data = 0;
while(*p >= '0' && *p <= '9')
{
data = data * 10 + *p - '0';
p++;
}
// printf("data = %d\n",data);
push_linkstack(operand,data);
continue;
}
if(*p == '+' || *p == '-' ||
*p == '*' || *p == '/')
{
deal_with(operand,operator,*p);
p++;
continue;
}
if(*p == '(')
{
push_linkstack(operator,*p);
p++;
continue;
}
if(*p == ')')
{
while(!is_empty_linkstack(operator) && get_top_data(operator) != '(')
{
compute(operand,operator);
}
if(is_empty_linkstack(operator))
{
/*printf("'(' lost\n");*/
return -2;
}
pop_linkstack(operator);
p++;
continue;
}
//printf("Invalid char %c\n",*p);
return -1;
}
while(!is_empty_linkstack(operator))
{
compute(operand,operator);
}
*pres = pop_linkstack(operand);
return 0;
}
int main()
{
char buf[N] = {0};
int result = 0;
int ret = 0;
printf("Input expression: ");
scanf("%99[^\n]",buf);
/*puts(buf);*/
if((ret = compute_expression(buf,&result)) < 0)
{
if(ret == -1)
{
printf("Invalid char\n");
}
else if(ret == -2)
{
printf("( lost\n");
}
return -1;
}
printf("%s = %d\n",buf,result);
return 0;
}
运行结果：