6.<1>四则运算的研究[栈]

计算1+2*3=，这个程序还是比较绕的，先将程序简化，只做+-*/和=五个运算符的关系。首先，假定这五个运算符中，=号的优先级最低，其次是+-，最高为*/。接着约定，"1+2*3="，为字符串。

第一步，将=号入栈，作为栈底。然后，再依次进行后续的比较。
约定：栈顶符号<字符串符号，则字符串符号入栈。栈顶符号>=字符串符号的，则进行计算！

分步来说，首先取字符1，为数字，则入数据栈，接着取字符+，由于初始化时，栈中只有一个=号，也即为栈顶，两者比较，根据约定，+号入符号栈，接着为2，入数据栈。接着*号，由于栈顶小于字符串的优先级，因为此时的栈顶是+号，所以*号入符号栈，再接着3，入数据栈，最后是等号。

直到等号时，字符串的符号才小于栈顶，根据约定要计算。

计算规则：
(1)符号栈，出（一个）栈顶符号
(2)数据栈取出两数据，配合栈顶符号进行计算。

根据计算规则，取出*号，然后，再取出3和2，得到6，并将之存入到数据栈中。
再拿栈顶与字符比较，此时，由于*号已经出栈，剩下+号，再比较，还是>字符串中的=号，所以再计算。得到1+6=7，将7入数据栈。此时，栈顶就是=号，然后再拿=号和=号进行比较，则循环判定结束，最后返回数据栈中的元素就是最后的结果！

/*-------------完整程序@映雪---2016/3/16-------------*/

#include <iostream>
using namespace std;
#define MAXSIZE 50
typedef struct stack
{
    int data[MAXSIZE];
    int top;
}Stack;
void init(Stack &s)
{
    s.top=-1;
}
void push(Stack &s,int e) /*入栈*/
{   s.data[++s.top]=e; }

int pop(Stack &s) /*出栈*/
{    return s.data[s.top--];}

int peek(Stack &s) /*取栈顶数据*/
{    return s.data[s.top];}

int check(char c) //检查字符是否为运算符 
{
    switch(c)
    {
        case'+':
        case'-':
        case'*':
        case'/':
        case'=':
            return 1;
            break;
        default:
            return 0;
            break;
    } 
}

int compare(char x,char c) //判断两个运算符的优先级
// oper1大于oper2的优先级，返回1 
//oper1小于oper2的优先级，返回-1
//oper1等于oper2的优先级，返回0 
{
    int pri;
    switch(c) //判断运算符优先级 
    {
        case '+':
        case '-':
            if(x=='('||x=='=') //为左括号或表达式开始符号 
                pri=-1; //返回小于 
            else 
                pri=1;
            break;
        case '*':
        case '/':
            if(x=='*'||x=='/'||x==')')
                pri=1;
            else
                pri=-1;
            break;
        case '=' :
            if(x=='(')
            {
                cout<<"括号不匹配!
";
                exit(0);
            }else if(x=='=')
                pri=0;
            else
                pri=1;
            break;
    }
    return pri; 
}
int Calc(int a,int oper,int b) //计算两个操作数的结果 
{
    switch(oper)
    {
        case'+':return a+b;
        case'-':return a-b;
        case'*':return a*b;
        case'/':
            if(b!=0)
               return a/b;
            else
            {
                cout<<"除0溢出!
";
                exit(0); 
            }  
    }
} 
int CalcExp(char exp[]) //表达式计算函数 
{
    Stack A,B;
    int i=0,flag=0;
    int a,b,t;/*a，b为数据栈中取出的数据,t为a与b的计算结果*/
    int c,q,x,oper;
    
    init(A); //初始化两个栈 
    init(B);

    q=0;
    x='=';
    push(B,x); //首先将等号(=)进入操作符栈  
    c=exp[i++];/*取字符串的第一个字符*/
    
    while(c!='=' || x!='=')/*判定最终完成计算的条件*/
    {
        if(check(c)) //若输入的是运算符 
        {
            if(flag) /*有未入栈的操作数，则操作数入栈*/
            {               
                push(A,q);//将操作数入栈 
                q=0;
                flag=0;
            }         
            switch(compare(x,c)) //判断运算符的优先级
            {
                case -1:
                    push(B,c);//运算符进栈 
                    c=exp[i++];
                    break;
                case 0:
                    c=pop(B); //运算符出栈 (抛弃)
                    c=exp[i++];
                    break;
                case 1:
                    oper=pop(B); //运算符出栈 
                    b=pop(A);//两个操作数出栈 
                    a=pop(A);
                    t=Calc(a,oper,b);
                    push(A,t);//运算结果入栈 
                    break;
            }
        }
        else if(c>='0'&&c<='9') //若输入字符在0~9之间 
        {
            c-='0';
            q=q*10+c;/* 计算数字的总数 */
            c=exp[i++];
            flag=1;
        }
        else
        {
            cout<<"输入错误!
";
            exit(0);
        }
        x=peek(B);//获取栈顶的运算符 
    }
    
    q=pop(A);/*出栈最终结果*/
    return q; 
} 

int main() 
{
    char exp[80];
    cout<<"请输入要计算的表达式(以=结束):"; 
    cin>>exp;
    cout<<exp<<CalcExp(exp);
    return 0;
}