表达式求值简单版

栈在表达式计算过程中的应用 ：建立操作数栈和运算符栈。运算符有优先级。规则：

• 自左至右扫描表达式，凡是遇到操作数一律进操作数栈。

• 当遇到运算符时，如果它的优先级比运算符栈栈顶元素的优先级高就进栈。反之，取出栈顶运算符和操作数栈栈顶的连续两个操作数进行运算，并将结果存入操作数栈，然后继续比较该运算符与栈顶运算符的优先级。
  

PPT课件链接:

链接：https://pan.baidu.com/s/1h8orxPVaVncDSvOJ2-Y4Xw

提取码：r31j

思路:

思考：如果我想要用栈实现下列公式的计算，该怎么办？
(注：这里先不考虑空格问题)
//1+123*5;
char buf[1024];

思考："123"如何转换成整型数123？
答案：
int data = 0;
for(i = 0;i < 3;i++){
data = data * 10 + buf[i] - '';
}


思路：
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.
",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 != '')
{
        //获得运算数
        if(*p >= '0' && *p <= '9')
        {
                        data = 0；                
        
                //获得运算数
                
                //入运算数栈
                
                continue;
        }
        
        if(*p == '+' || *p == '-' .....)
        {
                        //处理运算符
                        deal_with(operand,operator,*p);
                        p++;
                        continue;
        }
                        
}