zhuluoc 的学生作业：
// linkstack.h
#ifndef __LINKSTACK_H__
#define __LINKSTACK_H__
#include
#include
#include
//-----------------------------------------------
// 定义联合体，使用运算数与运算符共用一个结构创建链式栈
typedef union
{
char op;
int dt;
} u_data_t;
//-----------------------------------------------
// 链式栈节点结构体
typedef struct node
{
u_data_t data;
struct node *next;
} stacknode_t;
//-----------------------------------------------
// 链式栈结构体
typedef struct
{
stacknode_t *top;
int icnt;
} linkstack_t;
//-----------------------------------------------
// 创建空栈
extern linkstack_t *create_linkstack();
//-----------------------------------------------
// 判断栈是否为空
extern int is_empty_linkstack(linkstack_t *s);
//-----------------------------------------------
// 入栈
extern int push_linkstack(linkstack_t *s, u_data_t data);
extern int push_linkstack_int(linkstack_t *s, int data);
extern int push_linkstack_char(linkstack_t *s, char data);
//-----------------------------------------------
// 出栈
extern u_data_t pop_linkstack(linkstack_t *s);
extern int pop_linkstack_int(linkstack_t *s);
extern char pop_linkstack_char(linkstack_t *s);
//-----------------------------------------------
// 获取栈顶元素
extern u_data_t top_linkstack(linkstack_t *s);
extern int top_linkstack_int(linkstack_t *s);
extern char top_linkstack_char(linkstack_t *s);
//-----------------------------------------------
#endif
// linkstack.c
#include "linkstack.h"
//-----------------------------------------------
// 创建空栈
linkstack_t *create_linkstack()
{
linkstack_t *s = (linkstack_t *)malloc(sizeof(linkstack_t));
if (NULL == s)
{
printf("linkstack malloc error!\n");
return NULL;
}
memset(s, 0, sizeof(linkstack_t));
s->top = NULL; // 设置栈顶为空
s->icnt = 0;
return s;
}
//-----------------------------------------------
// 判断栈是否为空
int is_empty_linkstack(linkstack_t *s)
{
return (s->top == NULL ? 1 : 0);
}
//-----------------------------------------------
// 入栈
int push_linkstack(linkstack_t *s, u_data_t data)
{
stacknode_t *t = (stacknode_t *)malloc(sizeof(stacknode_t));
if (NULL == t)
{
printf("stacknode malloc error!\n");
return -1;
}
t->data = data;
// 插入数据
t->next = s->top;
s->top = t;
s->icnt++;
return 0;
}
//-----------------------------------------------
int push_linkstack_int(linkstack_t *s, int data)
{
u_data_t uda;
uda.dt = data;
return push_linkstack(s, uda);
}
//-----------------------------------------------
int push_linkstack_char(linkstack_t *s, char data)
{
u_data_t uda;
uda.op = data;
return push_linkstack(s, uda);
}
//-----------------------------------------------
// 出栈
u_data_t pop_linkstack(linkstack_t *s)
{
u_data_t data;
stacknode_t *t = NULL;
t = s->top;
data = t->data;
s->top = t->next;
free(t);
t = NULL;
s->icnt--;
return data;
}
//-----------------------------------------------
int pop_linkstack_int(linkstack_t *s)
{
u_data_t data = pop_linkstack(s);
return data.dt;
}
//-----------------------------------------------
char pop_linkstack_char(linkstack_t *s)
{
u_data_t data = pop_linkstack(s);
return data.op;
}
//-----------------------------------------------
// 获取栈顶元素
u_data_t top_linkstack(linkstack_t *s)
{
return s->top->data;
}
//-----------------------------------------------
int top_linkstack_int(linkstack_t *s)
{
return s->top->data.dt;
}
//-----------------------------------------------
char top_linkstack_char(linkstack_t *s)
{
return s->top->data.op;
}
//-----------------------------------------------
// calculate.h
#ifndef __CALCULATE_H__
#define __CALCULATE_H__
#include "linkstack.h"
//-----------------------------------------------
// 将字符数值转换为int
// buf[] --- 数值字符串
// len --- 数值字符串的长度
extern int chartoint(char buf[], int len);
// 判断是运行数，还是运算符
extern int is_op_digital(char c);
// 计算
extern int do_calculator(char *buf, int len);
// 根据操作符处理
extern void deal_operator(linkstack_t *opd, linkstack_t *opt, char op);
// 获取操作符优先级
extern int get_op_level(char op);
// 计算两个数的值
extern int compute(linkstack_t *opd, linkstack_t *opt);
#endif
// calculate.c
#include "calculate.h"
//-----------------------------------------------
// 将字符数值转换为int
// buf[] --- 数值字符串
// len --- 数值字符串的长度
int chartoint(char buf[], int len)
{
int i = 0, j = 0;
int data = 0, tmp = 0;
for (i = 0; i < len; i++)
{
tmp = 1;
for (j = 0; j < len - i - 1; j++)
tmp *= 10;
tmp *= (buf[i] - 48);
data += tmp;
}
return data;
}
//-----------------------------------------------
// 判断是运行数，还是运算符
int is_op_digital(char c)
{
int ret = -1;
switch (c)
{
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
ret = 1;
break;
case '.':
ret = 2;
break;
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
ret = 3;
break;
default:
ret = -1;
break;
}
return ret;
}
//-----------------------------------------------
// 计算
int do_calculator(char *buf, int len)
{
int i = 0, data = 0, dig_len = 0;
char c, dig[1024];
linkstack_t *opd = NULL, *opt = NULL;
// 创建运算数栈
opd = create_linkstack();
if (NULL == opd)
return 0;
// 创建运算符栈
opt = create_linkstack();
if (NULL == opt)
return 0;
// 解析计算字符串
for (i = 0; i < len; i++)
{
// 获取字符类型，是运算数，还是运算符
c = buf[i];
switch (is_op_digital(c))
{
case 1: // 数值
{
dig[dig_len++] = c; // 运算数字符串
break;
}
case 2: // 小数点
break;
case 3: // 操作符
{
// 将运算数压栈
if (dig_len > 0)
{
data = chartoint(dig, dig_len);
push_linkstack_int(opd, data);
dig_len = 0;
}
// 根据操作符处理计算过程
deal_operator(opd, opt, c);
break;
}
} // End of "switch (is_op_digital(buf[i]))"
} // End of "for (i = 0; i < len; i++)"
if (dig_len != 0)
{
// 将运算数压栈
data = chartoint(dig, dig_len);
push_linkstack_int(opd, data);
dig_len = 0;
}
while (!is_empty_linkstack(opt))
{
compute(opd, opt);
}
data = 0;
if (!is_empty_linkstack(opd))
{
data = pop_linkstack_int(opd);
// printf("%d\n", pop_linkstack_int(opd));
}
return data;
}
//-----------------------------------------------
// 根据操作符处理
void deal_operator(linkstack_t *opd, linkstack_t *opt, char op)
{
int ioplev = 0, itoplev = 0;
if (')' == op) // 右括号，不入栈，直接计算
{
while ('(' != top_linkstack_char(opt))
compute(opd, opt);
// 计算完后，左括号要出栈
pop_linkstack_char(opt);
}
else if ('(' == op) // 左括号，直接栈，不计算
{
push_linkstack_char(opt, op);
}
else if (is_empty_linkstack(opt)) // 运算符栈为空时，直接入栈
{
push_linkstack_char(opt, op);
}
else
{
ioplev = get_op_level(op);
itoplev = get_op_level(top_linkstack_char(opt));
if (ioplev > itoplev) // 当前运算符优先级大于栈顶运算符的优先级时，先入栈
{
push_linkstack_char(opt, op);
}
else
{
// 当前运算符优先级小于或等于栈顶运算符的优先及时，先计算
compute(opd, opt);
// 再将当前运算符入栈
push_linkstack_char(opt, op);
}
}
}
//-----------------------------------------------
// 获取操作符优先级
int get_op_level(char op)
{
int ret = -1;
switch (op)
{
case '(':
ret = 0;
break;
case '+':
case '-':
ret = 1;
break;
case '*':
case '/':
ret = 2;
break;
default:
ret = -1;
break;
}
return ret;
}
//-----------------------------------------------
// 计算两个数的值
int compute(linkstack_t *opd, linkstack_t *opt)
{
int i = 0;
int data = 0, data1 = 0, data2 = 0;
// char tmp = 0, cdt[1024];
// 运算数2出栈
data2 = pop_linkstack_int(opd);
// 运算数1出栈
data1 = pop_linkstack_int(opd);
// 运算符出栈
if (!is_empty_linkstack(opt))
{
switch (pop_linkstack_char(opt))
{
case '+':
data = data1 + data2;
break;
case '-':
data = data1 - data2;
break;
case '*':
data = data1 * data2;
break;
case '/':
data = data1 / data2;
break;
}
}
// 计算结果入栈，参与下次计算
push_linkstack_int(opd, data);
return 0;
}
//-----------------------------------------------
// main.c
#include
#include
#include
#include "linkstack.h"
#include "calculate.h"
//
int main()
{
char c;
char buf[1024];
int len = 0, data = 0;
while (1)
{
scanf("%c", &c);
if (c == '=' || c == '\n')
break;
buf[len++] = c;
}
// printf("buf=%s", buf);
data = do_calculator(buf, len);
printf("%s = %d", buf, data);
// buf[0] = '1';
// buf[1] = '2';
// buf[2] = '3';
// int data = chartoint(buf, 3);
// printf("data 0 = %d\n", data);
return 0;
}
运算结果
4+82-3
4+82-3 = 17
+18
