基于栈的表达式计算
思路:
设计一个运算符栈
设计一个数据栈
1.输入表达式
eg:
123 + 3 * 3 - 24
2.分析这个字符串
观察我们发现,每个数字都是一个字符,那如何 把123三个字符转换成123数字呢
提示:
int data = 0;
data = data * 10 + buf[i] - '0';
3.数字和运算符分别入栈
while(buf[i])
{
if(buf[i] >= '0' && buf[i] <= '9')
{
收集数据
}else{//遇到运算符
push_stack_data();
deal_with();//对运算符处理
}
}
观察一下,但遍历这个字符串结束后,最后一个数字是否入栈了。
push_stack_data();
last_deal_with();
__________________________________________________________________________
deal_with:
1.如果运算符的栈为空,直接将运算符入栈,然后返回
2.如果运算符栈不为空,当前的运算符能不能入栈,需要判断.
3.取出运算符栈顶的运算符和当前运算符进行优先级比较,如果有当前运算符优先级高,直接入栈,然后函数返回,否则calc_data,将计算的结果继续入数据栈,然后继续(注意,如果在操作过程中,运算符栈已经为空,这个时候当前运算符入栈,然后返回)。
calc_data:
从运算符栈中出一个operator,从数据栈中出两个data,然后进行运算,把运算的结果返回。
______________________________________________________________________________
last_deal_with:
经过我们以上的处理,此时运算符栈中的运算符应该都是同级的,此时我们只要
while(1)
{
if(!is_empty_operator_stack())
{
value = calc_data();
push_data_stack();
}else{
break;
}
}
这样最终数据栈中放的就是最后的运算结果
主程序从这里开始:
主体代码:
- #include <stdio.h>
- #include <stdlib.h>
- #include "datastack.h"
- #include "operstack.h"
- #define MAX 100
- int get_levle(char operator)
- {
- int level;
-
- switch(operator)
- {
- case '(':
- level = 0;
- break;
- case '+':
- case '-':
- level = 1;
- break;
- case '*':
- case '/':
- level = 2;
- break;
- }
- return level;
- }
- int calc_data(DataStack *p,OperatorStack *q)
- {
- char operator;
- int data1,data2;
- int value;
- data2 = pop_data_stack(p);
- data1 = pop_data_stack(p);
- operator = pop_operator_stack(q);
- #ifndef _DEBUG_
- printf(" %d %c %d\n",data1,operator,data2);
- #endif
- switch(operator)
- {
- case '+':
- value = data1 + data2;
- break;
- case '-':
- value = data1 - data2;
- break;
- case '*':
- value = data1 * data2;
- break;
- case '/':
- value = data1 / data2;
- break;
- }
- return value;
- }
- //1 + 2 * 3 + 4
- int deal_with(DataStack *pdata,OperatorStack *poper,char op)
- {
- int new_level;
- int old_level;
- int value;
-
- if(is_empty_operator_stack(poper))
- {
- push_operator_stack(poper,op);
- return 0;
- }
-
- while(1)
- {
- new_level = get_levle(op);
- old_level = get_levle(get_stack_top_operator(poper));
- if(new_level > old_level || is_empty_operator_stack(poper))
- {
- push_operator_stack(poper,op);
- return 0;
-
- }else{
- value = calc_data(pdata,poper);
- push_data_stack(pdata,value);
- }
- printf("value = %d\n",value);
- }
- return value;
- }
- int stack_init(DataStack *pdata,OperatorStack *poper)
- {
- init_data_stack(pdata);
- init_operator_stack(poper);
- return 0;
- }
- int last_deal_with(DataStack *pdata,OperatorStack *poper)
- {
- int value;
-
- while(1)
- {
- if(!is_empty_operator_stack(poper))
- {
- value = calc_data(pdata,poper);
- push_data_stack(pdata,value);
-
- }else{
-
- break;
- }
- }
- value = get_stack_top_data(pdata);
- return value;
- }
- int special_handing(DataStack *p,OperatorStack *q)
- {
- int value;
- char operator;
- while(1)
- {
- operator = get_stack_top_operator(q);
- if(operator == '(')
- {
- pop_operator_stack(q);
- break;
- }
-
- value = calc_data(p,q);
- printf("value = %d\n",value);
-
- push_data_stack(p,value);
- printf("top = %d\n",get_stack_top_data(p));
- }
- return 0;
- }
- int recive_data(char *p)
- {
- int data = 0;
- int i = 0;
- while(1)
- {
- if(!(p[i] >= '0' && p[i] <= '9') || p[i] == '\0')
- {
- break;
- }
- data = data * 10 + p[i] - '0';
- i ++;
- }
- return data;
- }
- int main()
- {
- char buf[MAX];
- int i = 0;
- int value;
- int data = 0;
- int flag = 0;
- DataStack *pdata = (DataStack *)malloc(sizeof(DataStack));
- OperatorStack *poper = (OperatorStack *)malloc(sizeof(OperatorStack));
- //输入数据
- while((buf[i++] = getchar()) != '\n' && i < MAX);
- buf[i-1] = 0;
- //栈初始化
- stack_init(pdata,poper);
- i = 0;
-
- while(buf[i])
- {
- //遇到空格继续下一个字符
- if(buf[i] == ' ')
- {
- i ++;
- continue;
- }
- //收集数据
- if(buf[i] >= '0' && buf[i] <= '9')
- {
- if(flag == 0)
- {
- data = recive_data(&buf[i]);
- push_data_stack(pdata,data);
- printf("data = %d\n",data);
- flag = 1;
- }
-
- }else{
- //处理()
- if(buf[i] == '(')
- {
- push_operator_stack(poper,buf[i]);
- i ++;
- continue;
- }
- if(buf[i] == ')')
- {
- special_handing(pdata,poper);
- i ++;
- continue;
- }
- //通用处理
- deal_with(pdata,poper,buf[i]);
- flag = 0;
- }
- i ++;
- }
- //最后一次处理,处理同级的运算符
- value = last_deal_with(pdata,poper);
- printf("value = %d\n",value);
-
- return 0;
- }
阅读(14424) | 评论(2) | 转发(15) |