题目描述


计算器1 简单的加减法
计算器2 简单的加减乘除
计算器3 包含括号和表达式有效性判断的加减乘除
计算器4 计算器3+乘方+取模

分析


4题有很多种解法,大致分为优雅的和不优雅的,不优雅的解法写到计算器3和计算器4的时候很容易就把自己给绕进去了。

本来,计算器1和2我之前做出来了,但是在当时算法的基础上处理计算器3的时候,遇到了太多的困难。(现在那代码我都不想再看第二眼)

具体实现方法就是,从左到右读,读运算符,累加,就这样……

优雅的解法中,最正规的应该是双栈直接求。但是这里我用的方法是 将中缀表达式转后缀表达式(逆波兰式),再对后缀表达式求值。之所以用这个方法求解,是因为但是我认为这种方法思路比较清晰简单,两步都不是很难。每一步都只需要一个栈。

一个题一个题来:


计算器1&2 P1373&P1374

P.S.:P1373只涉及加减法,非常简单,不一定非要用栈做,模拟也不是不可以。
如果用栈做的话,可以直接做1374。反正过1374的代码肯定是能过1373的。
实际上因为要求后缀表达式,这里实际上已经包含了1375的括号部分。

首先要把中缀表达式转后缀表达式:

string trans(string t) {
    t = '(' + t + ')';//以此略去处理结束后栈非空的情况
    string ret = "";
    map<char, int> m;
    m['+'] = m['-'] = 1;
    m['*'] = m['/'] = 2;
    m['('] = 9;//可以换成if switch 或者数组什么的方法来表示
    stack<char> s, tmp;
    for (auto it = t.begin(), e = t.end(); it != e; ++it) {
        if (isdigit(*it)) {
            for (; isdigit(*it); ret += *it, ++it);
            ret += ' ';
        }
        if (*it != ')') {
            while (1) {
				if(*it=='('&& *next(it) == '-')
					ret += "0 ";//处理0开头的情况
                if (s.empty() || s.top() == '(' || m[s.top()] < m[*it]) {
                    s.push(*it);
                    break;
                } else {
                    ret += s.top();
                    ret += ' ';
                    s.pop();
                }
            }
        } else {
            if (*prev(it) == '(') throw 0;
            if (s.empty()) throw 1;
            while (s.top() != '(') {
                if (s.empty()) throw 2;
                ret += s.top();
                ret += ' ';
                s.pop();
            }
            s.pop();
        }
    }
    if (!s.empty()) throw 3;

    return ret;
}

 

转化规则大致说说的话,就三点:

  1. 从左向右读中缀表达式,如果读入为一个数,直接输出到后缀表达式串中(注意空格);
  2. 如果读入为一个右括号,那么从栈中弹出元素到后缀表达式串中,直到栈顶元素为左括号,然后弹出左括号(不放入串中);
  3. 如果不是右括号,如果栈非空或栈顶元素为左括号,查看栈顶元素,如果栈顶元素的运算优先级大于或者等于该运算符号,则持续出栈,直到栈顶元素优先级小于该运算符。最后将该元素入栈

然后是后缀表达式求值:

void calc(string t) {
    t = trans(t);
    stack<int> s;
    for (auto it = t.begin(); isprint(*it); ++it) {
        if (!isgraph(*it)) continue;
        if (isdigit(*it)) {
            int a = 0;
            for (; isdigit(*it); a *= 10, a += *it - 48, it++);
            s.push(a);
        } else {
            int a, b;
            b = s.top();
            s.pop();
            a = s.top();
            s.pop();
            switch (*it) {
                case '+' :
                    s.push(a + b);
                    break;
                case '-' :
                    s.push(a - b);
                    break;
                case '*' :
                    s.push(a * b);
                    break;
                case '/' :
                    s.push(a / b);
                    break;
            }
        }
    }
    cout << s.top() << endl;
}

这个是没什么好说的……后缀表达式求值真的是太简单了,读到数入栈,读到运算符就从栈里拽出两个数来,算算,再扔进栈里去。最后找栈顶元素就好了。

可以用来测试的数据(此题坑不多):

  • -1-(-1) //如果没有处理好以负数开头的情况的话,会直接RE

没啥好说的……

计算器3 1375

说真的,1374做出来了, 1375就很快也能做出来了 【括号什么的早就在1374处理了喂(#`O′)

这里会出现一个新的问题:如何在已知表达式不合法的时候退出当前循环,输出”None”

Plan A: goto //别瞧不起goto

Plan B: if //说实话不好写

Plan C:Exception(try throw catch) //优雅,优雅

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <stack>
#include <vector>
#include <map>
#include <exception>

using namespace std;

string trans(string t) {
    t = '(' + t + ')';
    string ret = "";
    map<char, int> m;
    m['+'] = m['-'] = 1;
    m['*'] = m['/'] = m['%'] = 2;
    m['^'] = 3;
    m['('] = 9;
    stack<char> s, tmp;
    for (auto it = t.begin(), e = t.end(); it != e; ++it) {
        if (isdigit(*it)) {
            for (; isdigit(*it); ret += *it, ++it);
            ret += ' ';
        }
        if (*it != ')') {
            while (1) {
				if(*it=='('&& *next(it) == '-')
					ret += "0 ";
                if (s.empty() || s.top() == '(' || m[s.top()] < m[*it]) {
                    s.push(*it);
                    break;
                } else {
                    ret += s.top();
                    ret += ' ';
                    s.pop();
                }
            }
        } else {
            if (*prev(it) == '(') throw 0;
            if (s.empty()) throw 1;
            while (s.top() != '(') {
                if (s.empty()) throw 2;
                ret += s.top();
                ret += ' ';
                s.pop();
            }
            s.pop();
        }
    }
    if (!s.empty()) throw 3;

    return ret;
}

void calc(string t) {
    t = trans(t);
    stack<int> s;
    for (auto it = t.begin(); isprint(*it); ++it) {
        if (!isgraph(*it)) continue;
        if (isdigit(*it)) {
            int a = 0;
            for (; isdigit(*it); a *= 10, a += *it - 48, it++);
            s.push(a);
        } else {
            int a, b;
            if (s.size() < 2) throw 4;
                b = s.top();
                s.pop();
                a = s.top();
                s.pop();
            switch (*it) {
                case '+' :
                    s.push(a + b);
                    break;
                case '-' :
                    s.push(a - b);
                    break;
                case '*' :
                    s.push(a * b);
                    break;
                case '/' :
                    if (b == 0) throw 0;
                    s.push(a / b);
                    break;
            }
        }
    }
    if(s.size()!=1) throw 10;
    cout << s.top() << endl;
}

int main() {
    string s;
    while (cin >> s) {
        try {
            calc(s);
        } catch (int e) {
            cout << "None" << endl;
        }
    }
    return 0;
}

可以用来测试的数据(此题坑也不是很多):

  • 1++1
  • 1/0
  • 1/(1-1)
  • ()
  • (1+1))
  • 1+1+1+
  • 0/1

计算器4 P1376

实际上,这四个题如果按这个算法算下来的话,是非常顺的。

1376基本上就是1375缝缝补补后的样子。

需要单独判断一下乘方的优先级,别的没了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <vector>
#include <map>
#include <exception>

using namespace std;

bool cmp(char a, char b) {
    map<char, int> m;
    m['+'] = m['-'] = 1;
    m['*'] = m['/'] = m['%'] = 2;
    m['^'] = 3;
    m['('] = 9;
    if (a == b && a == '^') {
        return 1;
    } else return m[a] < m[b];
}

string trans(string t) {
    t = '(' + t + ')';
    string ret = "";
    stack<char> s, tmp;
    for (auto it = t.begin(), e = t.end(); it != e; ++it) {
        if (isdigit(*it)) {
            for (; isdigit(*it); ret += *it, ++it);
            ret += ' ';
        }
        if (*it != ')') {
            while (1) {
                if (*it == '(' && *next(it) == '-')
                    ret += "0 ";
                if (s.empty() || s.top() == '(' || cmp(s.top(), *it)) {
                    s.push(*it);
                    break;
                } else {
                    ret += s.top();
                    ret += ' ';
                    s.pop();
                }
            }
        } else {
            if (*prev(it) == '(') throw 0;
            if (s.empty()) throw 1;
            while (s.top() != '(') {
                if (s.empty()) throw 2;
                ret += s.top();
                ret += ' ';
                s.pop();
            }
            s.pop();
        }
    }
    if (!s.empty()) throw 3;
    return ret;
}

void calc(string t) {
    t = trans(t);
    stack<int> s;
    for (auto it = t.begin(); isprint(*it); ++it) {
        if (!isgraph(*it)) continue;
        if (isdigit(*it)) {
            int a = 0;
            for (; isdigit(*it); a *= 10, a += *it - 48, it++);
            s.push(a);
        } else {
            int a, b;
            if (s.size() < 2) throw 4;
            b = s.top();
            s.pop();
            a = s.top();
            s.pop();
            switch (*it) {
                case '+' :
                    s.push(a + b);
                    break;
                case '-' :
                    s.push(a - b);
                    break;
                case '*' :
                    s.push(a * b);
                    break;
                case '/' :
                    if (b == 0) throw 0;
                    s.push(a / b);
                    break;
                case '^' :
                    if (a == 0 && b == 0) throw 0;
                    s.push(pow(a, b));
                    break;
                case '%':
                    if (b == 0) throw 0;
                    s.push(a % b);
                    break;
            }
        }
    }
    if (s.size() != 1) throw 10;
    cout << s.top() << endl;
}

int main() {
    string s;
    while (cin >> s) {
        try {
            calc(s);
        } catch (int e) {
            cout << "None" << endl;
        }
    }
    return 0;
}

可以用来测试的数据(此题坑有点多了):

  • (-1)^(-1)
  • 1^(1-1)
  • (1-1)^(1-1)
  • (1-1)^(2-1)
  • 1+(-(1))
  • 1%0

无非就是摆弄那几个无意义的情况,没啥意思。

关于乘方的判断:可以认为优先级存在以下关系:
^(latter) > ^(former)

注意:

  • 0^0 无意义
  • 1^0 = 0
  • 1^(-1) = 1

暂时只想到这些。

b


但是这个题有一个问题定义不明:是否考虑“负号”的情况?即

1+-1

这样是否合法?

C语言中,这样是可以通过编译的。但是此题似乎并没有考虑这些。

CC BY-NC-SA 4.0 TSOJ 1373-1376 计算器 [表达式求值] by J. Chen is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.