前缀表达式计算

#include <iostream>
#include <cstdlib>
#include <string>
#include <stdexcept>
#include <vector>

using namespace std;

typedef enum _wordType {
    wT_Operator,
    wT_Number,
    wT_Parenthese
} wtype;

typedef union _wordValue {
    float f;
    char c;
} wvalue;

typedef struct _word {
    wvalue val;
    wtype type;
} word;

typedef vector<word> expression;
typedef vector<word> Stack;

#define isOperator(c)       ((c=='+')|| (c == '-')|| (c == '*')|| (c == '/'))   //|| (c == '|')|| (c == '%')|| (c == '^'))
#define isParenthese(c)     ((c=='(')||(c==')'))
#define isNumber(c)         ((c=='.')||isdigit(c))
#define getPriority(c)      (((c=='+')|| (c == '-'))?1:2)

#include <sstream>

template<class T>
string  to_string(const T& t)
{
    ostringstream oss;
    oss << t;
    string result = oss.str();
    return result;
}

bool str2exp(string strexp, expression &exp)
{
    if (strexp.empty())
        return false;
    string::iterator it = strexp.begin();
    int i = 0;
    while (it != strexp.end())
    {
        char c = *it;
        it++;
        if (isNumber(c))
        {
            if (!(exp.empty())&& ((exp[exp.size() - 1]).type == wT_Number))
            {
                printf("Invalid expressions! start:%d \n", exp.size()+1);
                return false;
            }
            word w;
            string strtemp;
            strtemp += c;
            w.type = wT_Number;
            while (it != strexp.end())
            {
                if (isNumber(*it))
                {
                    strtemp += (*it);
                    it++;
                }
                else if (((*it) == '\n') || ((*it) == '\r') || ((*it) == ' '))
                {
                    it++;
                }
                else
                {
                    break;
                }
            }
            w.val.f = strtof(strtemp.c_str(), 0);
            exp.push_back(w);
        }
        else if ((c == '\n') || (c == '\r') || (c == ' '))
        {
        }
        else
        {
            try
            {
                word w;
                w.type = (isOperator(c) ? wT_Operator : (isParenthese(c) ? wT_Parenthese : (throw "Invalide expressions word type")));
                w.val.c = c;
                exp.push_back(w);
            }
            catch (const char* e)
            {
                printf("%s! start:%d\n", e, exp.size() + 1);
                return false;
            }
        }
    }
    return true;
}

string in2pre(const expression exp_in, expression &exp_pre)
{
    if (exp_in.empty())
        return "";
    expression exp = exp_in;
    reverse(exp.begin(), exp.end());
    expression          charStack1, charStack2;     // char 类型的栈
    expression::iterator it = exp.begin();
    while (it != exp.end())
    {
        word c = *it;
        it++;
        if (c.type==wT_Number)
        {
            charStack2.push_back(c);
        }
        else if (c.type==wT_Operator)
        {
        lab1:
            if (charStack1.empty() || (charStack1.back().val.c == ')'))
            {
                charStack1.push_back(c);
            }
            else
            {
                char top = charStack1.back().val.c;
                if (getPriority(c.val.c) >= getPriority(top))
                {
                    charStack1.push_back(c);
                }
                else
                {
                    charStack2.push_back(charStack1.back()); charStack1.pop_back(); goto lab1;
                }
            }
        }
        else if (c.val.c == ')')
        {
            charStack1.push_back(c);
        }
        else if (c.val.c == '(')
        {
            word top;
            while (!charStack1.empty())
            {
                top = charStack1.back(); charStack1.pop_back();
                if ((top.type!=wT_Parenthese)||( top.val.c != ')'))
                    charStack2.push_back(top);
                else
                    break;
            }
        }
    }
    while (!charStack1.empty())
    {
        charStack2.push_back(charStack1.back()); charStack1.pop_back();
    }
    string strexp;
    while (!charStack2.empty())
    {
        word w = charStack2.back(); charStack2.pop_back();
        exp_pre.push_back(w);
        if (w.type == wT_Number)
        {
            strexp += to_string(w.val.f);
        }
        else
        {
            strexp += w.val.c;
        }
        strexp += "|";
    }
    //reverse(exp.begin(), exp.end());
    return strexp;
}

float calcprefixexp(const expression pre)
{
    if (pre.empty())
        return 0;

    vector<float> fStack;
    expression reverse_pre = pre;

    reverse(reverse_pre.begin(), reverse_pre.end());
    expression::iterator it = reverse_pre.begin();
    while (it != reverse_pre.end())
    {
        word c = *it;
        it++;
        if (c.type==wT_Number)
        {
            fStack.push_back(c.val.f);
        }
        else
        {
            float one, two;
            one = fStack.back();  fStack.pop_back(); two = fStack.back(); fStack.pop_back();
            switch (c.val.c)
            {
            case '+':
            {
                fStack.push_back(one + two);
                break;
            };
            case '-':
            {
                fStack.push_back(one - two);
                break;
            };
            case '*':
            {
                fStack.push_back(one * two);
                break;
            };
            case '/':
            {
                fStack.push_back(one / two);
                break;
            };
            default:
                break;
            }
        }
    }
    return fStack.back();
}

int main(int arc, char ** argv)
{
    expression exp_in, exp_pre;
    string strexp;
    char buff[1024];
    (argv[1]) ? (strexp = argv[1]) : (fgets(buff, 1024, stdin), fflush(stdin), strexp = buff);

    if (str2exp(strexp, exp_in))
    {
        string str_prefixexp = in2pre(exp_in, exp_pre);
        float ret = calcprefixexp(exp_pre);
        printf("%s=%.2f prefix expression:[%s]", strexp.c_str(), ret, str_prefixexp.c_str());
    }
}