codeup 1918 简单计算器

题目描述：
读入一个只包含 + ，-，×， / 的非负整数计算表达式，计算该表达式的值。
输入格式：
测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运草符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。
输出格式：
对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。
样例输入：
30 / 90 - 26 + 97 - 5 - 6 - 13 / 88 * 6 + 51 / 29 + 79 * 87 + 57 * 92
0
样例输出：
12178.21

思路
题目给出的是中缀表达式，所以要计算它的值主要是两个步骤：（如果不懂什么是前缀表达式和后缀表达式请看：https://www.cnblogs.com/chensongxian/p/7059802.html和https://www.cnblogs.com/zzliu/p/10801113.html）
①中缀表达式转后缀表达式。
②计算后缀表达式。
下面分别讲一下这两步。

步骤1：中缀表达式转后缀表达式
①设立一个操作符栈，用以临时存放操作符；设立一个数组或者队列，用以存放后缀表
达式。
②从左至右扫描中缀表达式，如果碰到操作数(注意：操作数可能不止一位，因此需要
一位一位读入然后合并在一起，具体实现见代码），就把操作数加入后缀表达式中。
③如果碰到操作符op，就将其优先级与操作符栈的栈顶操作符的优先级比较。
（1）若op的优先级高于栈顶操作符的优先级，则压入操作符栈。
（2）若op的优先级低于或等于栈顶操作符的优先级，则将操作符栈的操作符不断弹出到
后缀表达式中，直到op的优先级高于栈顶操作符的优先级。
④重复上述操作，直到中缀表达式扫描完毕，之后若操作符栈中仍有元素，则将它们依
次弹出至后缀表达式中。
（1）所谓操作符的优先级即它们计算的优先级，其中乘法 == 除法 > 加法==减法，在具体实
现上可以用map建立操作符和优先级的映射，优先级可以用数字表示，例如乘法和除法优先
级为1，加法和减法优先级为0。
（2）关于为什么当op高于栈顶时就压入操作符栈，这里举一个例子；
对中缀表达式3 + 2×5，显然如果先计算加法3 + 2会引起错误，必须先计算乘法2×5。当
从左到右扫描时，加号先进入操作符栈，而由于乘号优先级大于加号，其必须先计算，因此
在后缀表达式中乘号必须在加号前面，于是在栈中乘号要比加号更靠近栈顶，以让其先于加
号进入后缀表达式。
（3）关于为什么当op等于栈顶时不能直接压入操作符栈，这里举一个例子：
对中缀表达式2 / 3×4，如果设定优先级相等时直接压入操作符栈，那么算法步骤如下：
a)2进入后缀表达式，当前后缀表达式为2。
b) / 进入操作符栈，当前操作符栈为 /*。
c)3进入后缀表达式，当前后缀表达式为23。
d） * 与操作符栈的栈顶元素 / 比较，相等，压入操作符栈，当前操作符栈为/。
e)4进入后缀表达式，当前后缀表达式为234。
f)中缀表达式扫描完毕，操作符栈非空，将其全部弹入后缀表达式，最终后缀表达式变
为234*/。
g)计算该后缀表达式，发现其实变成了2 / (3×4），显然这跟原来中缀表达式的计算结果
完全不同。
（4）本题没有出现括号，但是如果出现括号，处理方法也很简单，遇到括号时：

，如果是左括号‘(’，就压入操作符栈；如果是右括号‘）’，就把操作符栈里的元
素不断弹出到后缀表达式直到碰到左括号‘(’ ，此时将这一对括号丢弃。

步骤2：计算后缀表达式
从左到右扫描后缀表达式，如果是操作数，就压入栈；如果是操作符，就连续弹出两个操作数(注意：后弹出的是第一操作数，先弹出的是第二操作数），然后进行操作符的操作，
生成的新操作数压入栈中。反复直到后缀表达式扫描完毕，这时栈中只会存在一个数，就是最终的答案。
（1）注意除法可能导致浮点数，因此操作数类型要设成浮点型。
（2）题目中说肯定是合法表达式，因此上面操作一定能够成功。但如果题目表明可能出现
非法表达式，那就要注意每一步使用的对象是否合法。

#include<iostream>

#include<string>

#include<stack>

#include<fstream>

#include<queue>

#include<map>

using namespace std;

struct node {

    double num;

    char op;

    bool flag;

};

string str;                                //中缀表达式

stack<node> s;                            //操作符栈

queue<node> q;                            //后缀表达式序列

map<char, int> oop;                        //操作符和优先级的映射 

void change() {                            //将中缀表达式转换为后缀表达式

    node temp;

    for (int i = 0; i < str.length();) {

        if (str[i] >= '0' && str[i] <= '9') {

            temp.flag = true;

            temp.num = str[i++] - '0';//记录这个操作数的第一个数位

            while (i < str.length() && str[i] >= '0' && str[i] <= '9') {

                temp.num = temp.num * 10 + (str[i] - '0');//更新这个操作数

                i++;

            }

            q.push(temp);

        }

        else {

            temp.flag = false;

            //只要操作符栈的栈顶元素比该操作符优先级高。

            //就把操作符栈顶元素弹出到后缀表达式的队列中。

            while (!s.empty() && oop[str[i]] <= oop[s.top().op]) {

                q.push(s.top());

                s.pop();

            }

            temp.op = str[i];

            s.push(temp);//将操作符压入栈。

            i++;

        }

    }

    while (!s.empty()) {//如果操作符栈中还有元素就把他弹出到后缀表达式队列中。

        q.push(s.top());

        s.pop();

    }

}

double cal() {//计算后缀表达式

    double temp1, temp2;

    node cur, temp;

    while (!q.empty()) {//只要后缀表达式非空

        cur = q.front();//cur记录首元素

        q.pop();

        if (cur.flag == true) s.push(cur);//如果是数字直接入栈。

        else {//如果是操作符

            temp2 = s.top().num;//弹出第二操作数

            s.pop();，

            temp1 = s.top().num;//弹出第一操作数，第一操作数在运算符前面。即次顶元素在运算符的前面，这一点与前缀表达式不同。

            s.pop();

            temp.flag = true;

            if (cur.op == '+') temp.num = temp1 + temp2;//做加法

            else if (cur.op == '-') temp.num = temp1 - temp2;//做减法

            else if (cur.op == '*') temp.num = temp1 * temp2;//做乘法

            else temp.num = temp1 / temp2;//做除法

            s.push(temp);//再将这个操作数压入栈

        }

    }

    return s.top().num;//栈顶元素便是后缀表达式的值

}

int main() {

    oop['+'] = oop['-'] = 1;//设定操作符的优先级

    oop['*'] = oop['/'] = 2;

    //    freopen("d://in.txt","r",stdin);

    while (getline(cin, str), str != "0") {

        for (string::iterator it = str.begin(); it != str.end(); it++) {

            if (*it == ' ') str.erase(it);//把表达式中的空格全部去掉。

        }

        while (!s.empty()) s.pop();//将栈初始化

        change();//将中缀表达式转化为后缀表达式

        printf("%.2f\n", cal());//计算并 输出后缀表达式的值

    }

    return 0;

}

//若中缀表达式中存在着括号：
void change() {                            //将中缀表达式转换为后缀表达式

    node temp;

    for (int i = 0; i < str.length();) {

        if (str[i] == '(') {

            temp.op = '(';

            s.push(temp);
            i++;

        }

        else if (str[i] == ')') {

            while (s.top().op != '(') {

                q.push(s.top());
                   s.pop();

            }

            s.pop();
              i++;

        }

        else if (str[i] >= '0' && str[i] <= '9') {

            temp.flag = true;

            temp.num = str[i++] - '0';//记录这个操作数的第一个数位

            while (i < str.length() && str[i] >= '0' && str[i] <= '9') {

                temp.num = temp.num * 10 + (str[i] - '0');//更新这个操作数

                i++;

            }

            q.push(temp);

        }

        else {

            temp.flag = false;

            //只要操作符栈的栈顶元素比该操作符优先级高。

            //就把操作符栈顶元素弹出到后缀表达式的队列中。

            while (!s.empty() && oop[str[i]] <= oop[s.top().op]) {

                q.push(s.top());

                s.pop();

            }

            temp.op = str[i];

            s.push(temp);//将操作符压入栈。

            i++;

        }

    }

    while (!s.empty()) {//如果操作符栈中还有元素就把他弹出到后缀表达式队列中。

        q.push(s.top());

        s.pop();

    }

}

前缀表达式是从右至左扫描中缀表达式的，如果中缀表达式要转换为前缀表达式不太方便。

若将中缀表达式转换为前缀表达式：

步骤一：

初始化两个栈:运算符栈s1，储存中间结果的栈s2（上面转换为后缀表达式时采用的是队列的方式储存后缀表达式，如果也采用栈的形式的话，输出结果的逆序才是后缀表达式）
从右至左扫描中缀表达式
遇到操作数时，将其压入s2
遇到运算符时，比较其与s1栈顶运算符的优先级
1. 如果s1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈
2. 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入s1
3. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较
遇到括号时
1. 如果是右括号“)”，则直接压入s1
2. 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃
重复步骤2至5，直到表达式的最左边
将s1中剩余的运算符依次弹出并压入s2。
依次弹出s2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

前缀表达式的计算机求值：

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素，栈顶元素在运算符前这一点与后缀运算符不同），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

巴特西

codeup 1918 简单计算器

前缀表达式的计算机求值：

最新文章

热门文章