#include "stdafx.h"
#include<iostream>
#include<stack>
using namespace std;
#define ERROR -1
#define RIGHT 0

#define CHECK_EMPTY(stack) if (stack.empty()) \
{    return ERROR;}

//用来输出提示信息的
#define PRINT_STEP 0

//判断是否为操作符
int IsOperator(char cTemp)
{
    switch (cTemp)
    {
    case ‘+‘:
    case ‘-‘:
    case ‘*‘:
    case ‘/‘:
    case ‘(‘:
    case ‘)‘:return 1;
    default:return 0;
    }
}

int JudgeOperatorPriority(char cOpe)
{
    switch (cOpe)
    {
    case ‘+‘:
    case ‘-‘:return 1;
    case ‘*‘:
    case ‘/‘:return 2;
    default:return ERROR;
    }
}

int Calculate(int lNum, int rNum, char cOper)
{
    int iResule = 0;
    switch (cOper)
    {
    case ‘+‘:
        iResule = lNum + rNum; break;
    case ‘-‘:
        iResule = lNum - rNum; break;
    case ‘*‘:
        iResule = lNum * rNum; break;
    case ‘/‘:
        iResule = lNum / rNum; break;
    default:
        return ERROR;
    }
    return iResule;
}

//进行优先级高的运算
int PartialCalc(stack<int>& iStack, stack<char>& cStack)
{
    int rNum = 0, lNum = 0, iResult = 0;
    char cOper;
    CHECK_EMPTY(iStack);
    rNum = iStack.top();
    iStack.pop();
    CHECK_EMPTY(iStack);
    lNum = iStack.top();
    iStack.pop();
    CHECK_EMPTY(cStack);
    cOper = cStack.top();
    cStack.pop();
    iResult = Calculate(lNum, rNum, cOper);
    iStack.push(iResult);
    return RIGHT;
}

int CompareOperator(char cStackOper, char cNewOper)
{
    return JudgeOperatorPriority(cStackOper) < JudgeOperatorPriority(cNewOper);
}

/*****************************************************
*函数名：ExpCalc
*功  能：给表达式求值
*入  参：pcExp: 表达式字符串，比如 1+2*3+4*5+6
*出  参：piResult:  表达式的运算结果
*返回值：RIGHT  执行成功
ERROR 执行失败
*创建日期：2017.3.11
*******************************************************/
int  ExpCalc(char *pcExp, int *piResult)
{
    if (PRINT_STEP)
    {
        cout << pcExp << endl;
    }

    if (pcExp == NULL || piResult == NULL)
    {
        return ERROR;
    }
    //用来保存操作数
    stack<int>iStackNum;
    //用来保存操作符
    stack<char>cStackOpe;
    int i = 0;
    int iRet;
    
    //当表达式第一个数为负数的时候，在操作数栈中压入一个0
    if (pcExp[0] == ‘+‘ || pcExp[0] == ‘-‘)
    {
        iStackNum.push(0);
    }

    while (pcExp[i])
    {
        //如果字符为数字
        if (pcExp[i] - ‘0‘ >= 0 && pcExp[i] - ‘0‘ <= 9)
        {
            if (PRINT_STEP)
            {
                cout << "num=" << pcExp[i] << endl;
            }
            int iSum = pcExp[i] - ‘0‘;
            i++;
            while (pcExp[i] - ‘0‘ >= 0 && pcExp[i] - ‘0‘ <= 9)
            {
                iSum *= 10;
                iSum += (pcExp[i] - ‘0‘);
                i++;
            }
            iStackNum.push(iSum);
            if (PRINT_STEP)
            {
                cout << "iStackNum.push=" << iSum << endl;
            }
            continue;
        }//end 最外层if
         //如果字符为操作符
        else if (IsOperator(pcExp[i]))
        {
            if (PRINT_STEP)
            {
                cout << "operator = " << pcExp[i] << endl;
            }
            //如果刚开始运算栈中没用运算符
            //或者比较栈中的运算符和新的运算符的优先级
            //如果栈顶运算符优先级比新的运算符低，直接压入栈中
            if (cStackOpe.empty()|| CompareOperator(cStackOpe.top(), pcExp[i])
                ||pcExp[i]==‘(‘)
            {
                cStackOpe.push(pcExp[i]);
                i++;

                if (cStackOpe.top() == ‘(‘ && (pcExp[i] == ‘-‘ || pcExp[i] == ‘+‘))
                {
                    iStackNum.push(0);
                }
                continue;
            }
            else if (pcExp[i] == ‘)‘)
            {
                while (cStackOpe.top() != ‘(‘)
                {
                    //开始进行部分的运算
                    iRet=PartialCalc(iStackNum, cStackOpe);
                    if (iRet != RIGHT)
                    {
                        return iRet;
                    }
                    CHECK_EMPTY(cStackOpe);
                }
                cStackOpe.pop();
                i++;
                continue;
            }
            //如果栈顶运算符优先级比新的运算符高
            else
            {
                //开始进行部分的运算
                iRet = PartialCalc(iStackNum, cStackOpe);
                if (iRet != RIGHT)
                {
                    return iRet;
                }
                continue;
            }
        }//end else if (IsOperator(pcExp[i]))
        else
        {
            //忽略所有不是操作数或者运算符的字符
            i++;
        }
    }//end while(acExp[i])
     //如果运算符栈中用运算符，继续运算，直到运算栈为空
    while (!cStackOpe.empty())
    {
        iRet=PartialCalc(iStackNum, cStackOpe);
        if (iRet != RIGHT)
        {
            return iRet;
        }
    }
    if (iStackNum.size() > 1)
    {
        return ERROR;
    }
    *piResult = iStackNum.top();
    return RIGHT;
}


int main()
{
    int iRet = 0;;

    ExpCalc("1+2*3+4*5*6+7*8-100", &iRet);
    cout << "1+2*3+4*5*6+7*8-100 = " << iRet << endl;
    cout << "Check: " << (1 + 2 * 3 + 4 * 5 * 6 + 7 * 8 - 100) << endl;
    ExpCalc("100+90*12*2-1000", &iRet);
    cout << "100+90*12*2-1000 = " << iRet << endl;
    cout << "Check: " << (100 + 90 * 12 * 2 - 1000) << endl;

    //增加括号运算符
    ExpCalc("(1+2)*(3+4)*5*6+7*8-100", &iRet);
    cout << "(1+2)*(3+4)*5*6+7*8-100 = " << iRet << endl;
    cout << "Check: " << ((1 + 2)*(3 + 4) * 5 * 6 + 7 * 8 - 100) << endl;

    //增加负数处理
    char szExp3[] = "-1+ 3*((-2*3+4)*(5+6*(3+2)*4+(-10)))-(100+4*5)*2";
    ExpCalc(szExp3, &iRet);
    cout << szExp3 << " = " << iRet << endl;
    cout << "Check:" << (-1 + 3 * ((-2 * 3 + 4)*(5 + 6 * (3 + 2) * 4 + (-10))) - (100 + 4 * 5) * 2) << endl;
    cout << endl;

    //非法表达式
    char szExp4[] = "1-+2*3";
    char szExp4[] = "1+2*(3+4)5";
    char szExp4[] = "1+2*(3+4"; 
    char szExp4[] = "1+2*3+4*5)"; 
    int iTmp = ExpCalc(szExp4, &iRet);
    if (iTmp)
    {
        cout << "Expression [" << szExp4 << "] error!" << endl;
    }
    else
    {
        cout << szExp4 << " = " << iRet << endl;
    }
    cout << endl;
    return 0;
}