慕工程6300203 的学生作业:
#include
#include
#include
typedef int data_t;
/**
* 链表节点
*/
typedef struct link_node
{
data_t data;
struct link_node* next;
} link_node_t;
/**
* 栈头
*/
typedef struct stack
{
link_node_t *top;
int n;
} stack_t;
/**
* 获取优先级
* @param operator
* @return
*/
int get_level(char operator)
{
switch(operator)
{
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
default:
printf("Invalid operator : %c.\n",operator);
return -1;
}
}
/**
* 创建
* @return
*/
stack_t *create_empty_link_stack()
{
stack_t *s = NULL;
s = (stack_t *)malloc(sizeof(stack_t));
if(NULL == s)
{
printf("malloc is failed!");
}
memset(s,0,sizeof(stack_t));
return s;
}
/**
* 判空
* @param s
* @return
*/
int is_empty_stack(stack_t *s)
{
return s->n == 0 ? 1 : 0;
}
/**
* 新增数据
* @param s
* @param data
* @return
*/
int push(stack_t *s, data_t data)
{
link_node_t *temp = NULL;
temp = (link_node_t *) malloc(sizeof(link_node_t));
if(NULL == temp)
{
printf("malloc is failed!");
return -1;
}
temp->data = data;
temp->next = s->top;
s->top = temp;
s->n++;
return 0;
}
/**
* 删除数据
* @param s
* @return
*/
data_t pop(stack_t *s)
{
if (is_empty_stack(s))
{
printf("stack is empty!");
return -1;
}
link_node_t *temp = NULL;
data_t data;
temp = s->top;
data = temp->data;
s->top = temp->next;
free(temp);
temp = NULL;
s->n--;
return data;
}
/**
* 获取栈顶元素
* @param s
* @return
*/
data_t get_top_data(stack_t *s) {
return s->top->data;
}
/**
* 判断是否是运算符
* @param c
* @return
*/
int is_char(char c)
{
switch(c)
{
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
return 1;
default:
return 0;
}
}
/**
* 计算
* @param operand
* @param operator
*/
int compute(stack_t *operand, stack_t *operator)
{
data_t data1;
data_t data2;
data_t opt;
data_t result = 0;
data2 = pop(operand);
data1 = pop(operand);
opt = pop(operator);
switch (opt)
{
case '+':
result = data1 + data2;
break;
case '-':
result = data1 - data2;
break;
case '*':
result = data1 * data2;
break;
case '/':
result = data1 / data2;
break;
default: ;
}
push(operand, result);
return result;
}
/**
* 处理运算符
*
* 若是操作符(考虑优先级问题)
* 当遇到运算符时,如果它的优先级比运算符栈栈顶元素的优先级高就进栈。
* 反之,取出栈顶运算符和操作数栈栈顶的连续两个操作数进行运算,
* 并将结果存入操作数栈,然后继续比较该运算符与栈顶运算符的优先级。
*
* 左括号一律进运算符栈,
* 右括号一律不进运算符栈,取出运算符栈顶运算符和操作数栈顶的两个操作数进行运算,并将结果压入操作数栈,直到取出左括号为止。
*
* @param operand
* @param operator
* @param opt
* @param p
*/
void deal_with(stack_t *operand,stack_t *operator,char opt)
{
// 栈为空,直接入栈
if (operator->n == 0)
{
push(operator, opt);
}
// 左括号一律进运算符栈,
else if (opt == '(')
{
push(operator, opt);
}
// 右括号一律不进运算符栈,取出运算符栈顶运算符和操作数栈顶的两个操作数进行运算,并将结果压入操作数栈,直到取出左括号为止。
else if (opt == ')')
{
do
{
compute(operand, operator);
} while (get_top_data(operator) != '(');
pop(operator);
}
// 当遇到运算符时,如果它的优先级比运算符栈栈顶元素的优先级高就进栈。
// 反之,取出栈顶运算符和操作数栈栈顶的连续两个操作数进行运算,
// 并将结果存入操作数栈,然后继续比较该运算符与栈顶运算符的优先级。
else if (operator->top->data != '(' && get_level(opt) top->data))
{
compute(operand, operator);
deal_with(operand, operator, opt);
}
else if (operator->top->data == '(' || get_level(opt) > get_level(operator->top->data))
{
push(operator, opt);
}
}
data_t get_data(char c, data_t data)
{
return data * 10 + (c - '0');
}
int main()
{
char buf[1024];
char *p = buf;
int data = 0; //运算数
stack_t *operand = NULL, *operator = NULL;
operand = create_empty_link_stack();
operator = create_empty_link_stack();
//输入数据到buf中
printf("please input expression:");
gets(buf);
while(*p != '\0')
{
// 若是运算数,合并成一个完整的数data。
// 规则:直接入操作数栈
//获得运算数
if(*p >= '0' && *p n >= 2)
{
compute(operand, operator);
}
printf("result:%d\n", get_top_data(operand));
free(operand);
operand = NULL;
free(operator);
operator = NULL;
return 0;
}