题解 | #简单计算器#

#include<iostream>
#include<stack>
#include<string>
#include<cctype>
//isdigit()函数在头文件中cctype中
//该函数能够用来检查字符是否为十进制数字字符
using namespace std;

/*
 * 《算法笔记》p245 第七章 提高篇（1）————数据结构专题（1）
 * 7.1 栈的应用：【Codeup 1918】简单计算器
 * http://codeup.cn/problem.php?cid=100000605&pid=0
 * 题目描述：读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。
 *
 * 思路（王道）：
 * （1）两个栈，符号栈和数字栈。两个哨兵'#'和'￥'，'#'压入栈底(其优先级最低)，'$'接在串后(其优先级次低)，优先级'$'>'#'。
 * （2）优先级获得函数：'#'=0，'￥'=1，'+''-'=2，'*''/'=3。
 * （3）获取数字函数
 * （4）加减乘除计算函数
 * （5）从左至右遍历字符串，遇到空格则跳过；遇到数字则压入数字栈；
 *      如果遇到的是符号，则比较当前op与操作符栈顶opTop的优先级
 *      1）若果op>opTop，则将op入栈 (当前op优先级更高)
 *      2）如果op<=opTop，则弹出opTop，(栈顶op优先级更高)
 *          并弹出数字stack的栈顶和次栈顶，次栈顶为参与运算的在!前!数字，栈顶数字在!后!。
 *        计算结果存入数字stack。
 * （6）直到遍历结束，此时操作符stack中只剩'$''#'，且此时数字stack中只剩一个元素，即为结果。
 */
string exp;

int getPri(char c) {
    if (c == '#') {
        return 0;
    } else if (c == '$') {
        return 1;
    } else if (c == '+' || c == '-') {
        return 2;
    } else if (c == '*' || c == '/') {
        return 3;
    } else {
        return -1; //与题意无关
    }//最后一个必须用else,否则不是所有control path都有返回值
}

double getNumber(int&
                 index) { //index使用引用传参，可以改变传过来的实参的值，在函数中完成自增
    double number = 0;
    while (isdigit(exp[index])) {
        number = number * 10 + exp[index] - '0';
        index++;
    }
    return number;
}

double cal(double x, double y, char op) {
    //double res=0;
    if (op == '+') {
        return x + y;
    } else if (op == '-') {
        return x - y;
    } else if (op == '*') {
        return x * y;
    } else if (op == '/') {
        return x / y;
    } else {
        return 0; //与题意无关
    }
}



int main() {
    while (getline(cin,
                   exp)) { //整数和运算符之间用' '分割，无法用cin
        if (exp == "0") {
            break;
        }
        stack<double> data;   //每次循环重新定义，否则每次都要先清空
        stack<char> ops;
        exp += '$'; //string类重载了+
        ops.push('#');
        int index = 0;
        while (index < exp.size()) {
            if (exp[index] == ' ') {
                index++;
            } else if (isdigit(exp[index])) {
                data.push(getNumber(index));
            } else { //运算符
                if (getPri(exp[index]) > getPri(ops.top())) {
                    //当前运算符优先级更高
                    ops.push(exp[index]);
                    index++;
                } else if (getPri(exp[index]) <= getPri(ops.top())) {
                    //进行当前栈顶运算符对应的运算运算
                    double y = data.top();
                    data.pop();
                    double x = data.top();
                    data.pop();
                    data.push(cal(x, y, ops.top()));
                    ops.pop();
                    //注意，这里执行完还没有把当前运算符放到栈中，还要仅需和前一个做判断
                    //这样一来只要有'$'（比所有输入的运算符优先级都低）就肯定会把前面所有的都算完才入栈
                    //直到只剩'#'，才让'$'入栈
                }
            }
        }
        printf("%.2f\n", data.top());
    }
}
前后哨兵'#'、'$'的思想非常关键
每次循环重新定义，省得清理和初始化
string stack会导致dev-c++无法调试
字符串转实数很关键
注意if条件中要用==不是=
注意要保证所有控制路径(if else)都有返回值，否则有些oj可能会编译失败