中缀表达式转后缀表达式并求值

　　代码都是自解释的，重要函数也有注释，我就不多说了。

/** * 表达式求值系统 * A 类题：表达式求值系统 * 实现一个基本的表达式求值系统，要求从键盘读入带有括号的中 * 缀表达式，要求首先判断括号是否匹配，如果括号匹配表达式合法， * 再将中缀表达式转换为后缀表达式，并计算和输出表达式的值。对常 * 见输入错误的判断，比如：括号错误、非法字符、运算符号错误、除 * 数为零等错误情况。 * （1） 使用自己实现的栈或使用 STL 中的栈； * （2） 对输入的中缀表达式进行括号匹配判断，匹配输出 YES，否则输出 NO； * （3） 使用栈将中缀表达式转换为后缀表达式，并输出后缀表达式； * （4） 对后缀表达式进行计算并输出； */
#ifdef LOCAL
#include <fstream>
#endif // LOCAL
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>

using namespace std;
const int MAXN = 2000;
const char operators[] = "()+-/*";
stack<char> s; // operators stack.

void readDataAndDeal();
bool match(string &infixStr);
bool isOperator(char ch);
void convertToSuffix(const string &source, string &dest);
int getPriority(char ch);
double calculate(const string &suffixStr);

int main() {
#ifdef LOCAL
    freopen("A4in.txt", "r", stdin);
#endif // LOCAL
    readDataAndDeal();
    return 0;
}

/** * read the data and deal with them. */
void readDataAndDeal() {
    char temp[MAXN];
    fgets(temp, MAXN, stdin);
    string infixStr(temp), suffixStr;
    if (match(infixStr))
        printf("YES\n");
    else {
        printf("NO\n");
        return;
    }
    convertToSuffix(infixStr, suffixStr);
    printf("%s\n", suffixStr.c_str());
    printf("%f\n", calculate(suffixStr));
}

/** * If infixStr[i] is '(': push stack. * If infixStr[i] is ')': pop stack. * If the stack isn't empty: match failed. * operators[0] = '(' , operators[1] = ')' * @param infixStr - the infix string. * @return bool - true if infix string is valid. */
bool match(string &infixStr) {
    while (!s.empty())
        s.pop();
    for (size_t i = 0; i < infixStr.size(); i++) {
        if (isspace(infixStr[i])) continue;
        if (isdigit(infixStr[i]) || isOperator(infixStr[i])) {
            if (infixStr[i] == operators[0])
                s.push(operators[0]);
            else if (infixStr[i] == operators[1]) {
                if (!s.empty())
                    s.pop();
                else
                    return false;
            }
        } else
            return false;
    }
    if (!s.empty())
        return false;
    return true;
}

/** * Judge the ch is '+', '-', '*', '/', '(', ')' or not. * @param ch - the judge char. * @return true if is operators. */
bool isOperator(char ch) {
    for (size_t i = 0; i < sizeof(operators) / sizeof(char); i++) {
        if (ch == operators[i])
            return true;
    }
    return false;
}

/** * @param source - infix string * @param dest - suffix string * Read an infix expression from left to right. * (2)If it's an operator, append to the dest string with space. * (3)If it's operator '(', push it to stack. * (4)If it's operator ')', pop the stack and append to dest string until * the top element is '(', remove the '('. * (5)If it is not a bracket operator, compare their priorities with the stack top elements: * (a)If hight than top element, push it to stack. * (b)If low or equal than top element, append it to dest until the top * element is '(' or the stack is empty. * (6)If the stack isn't empty, pop and append it to dest until stack empty. */
void convertToSuffix(const string &source, string &dest) {
    while (!s.empty()) //clear stack
        s.pop();
    bool addSpace = false;
    for (size_t i = 0; i < source.size(); i++) {
        if (isspace(source[i])) continue;
        if (isdigit(source[i])) {
            if (addSpace) {
                dest += ' ';
                addSpace = false;
            }
            dest += source[i];
        }
        else if (source[i] == '(')
            s.push('(');
        else if (source[i] == ')') {
            while (s.top() != '(') {
                dest = dest  + ' ' + s.top();
                s.pop();
            }
            s.pop();// delete the '('
        } else {
            addSpace = true;

            while (!s.empty()) {
                int oldChar = getPriority(s.top());
                int newChar = getPriority(source[i]);
                if (oldChar < newChar || s.top() == '(') {
                   s.push(source[i]);
                   break;
                }
                else {
                    dest = dest  + ' ' + s.top();
                    s.pop();
                }
            }
            if(s.empty())s.push(source[i]);
        }
    }
    while (!s.empty()) {
        dest = dest  + ' ' + s.top();
        s.pop();
    }
}

/** * @param ch - the operator char * @return digit - the priority of operator char */
int getPriority(char ch) {
    if (ch == '+' || ch == '-')
        return 0;
    else
        return 1;
}
/** * @param suffixStr - the suffix string. * @return double - the calculate result. * If the element is number, push to stack. * (2)If the element is operator , pop two elements with a and b, calculate them. */
double calculate(const string &suffixStr) {
    stack<double> s;
    char ss[MAXN];
    strcpy(ss, suffixStr.c_str());
    char *p = NULL;
    p = strtok(ss, " ");
    while (p != NULL) {
        //printf("%s\n", p);
        if (isOperator(p[0])) {
            double b = s.top();
            s.pop();
            double a = s.top();
            s.pop();
            switch(p[0]) {
                case '+': s.push(a + b); break;
                case '-': s.push(a - b); break;
                case '*': s.push(a * b); break;
                case '/': {
                    if (b == 0) {
                        printf("you can't div by zero!\n");
                        return 0;
                    }else {
                        s.push(a / b);
                        break;
                    }
                }

            }
        } else {
            s.push(strtod(p, NULL));
        }
        p = strtok(NULL, " ");
    }
    return s.top();
}