基于栈的表达式计算

转载请注明来源chengyaogen.blog.chinaunix.net

 

基于栈的表达式计算

思路：

        设计一个运算符栈

        设计一个数据栈

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;
}