使用递归计算中缀表达式

数据结构作业

虽然我遵循着“作业截至即公开”的原则,但这次代码写得比较个性化(俗称”骚”),不容易涉及作业雷同,所以提前就post了出来。

设计思路

鲁迅说过:树都能用递归解决。

鲁迅还说过:不能重复造轮子。

根据以上两个原则,再加上我写过几次经典的中缀表达式计算了(就是用栈算后缀表达式再算值那种经典套路),所以我决心使用递归来处理这个问题。

同时,解题也是用的“刷算法题”代码模式,而不是我一贯使用的“项目式”的代码套路。这次的代码更强调技巧和效果,而不是重用和鲁棒。

  1. 确定算法大致方向 后序的计算一棵树
  2. 任务解耦 要算一个四则运算的中缀表达式,可以把任务分成几块
    1. 计算加减法
    2. 计算乘除法
    3. 获得叶子节点(或者把括号里的打包,当叶子)
  3. 处理一些特殊问题
    1. 带括号的:直接把括号内的拿出来算,算完以后当叶子节点放回原树
    2. 输出后缀表达式:在找到叶子时,将数字输出;在产生计算时,将计算符号输出,即构成后缀表达式

代码

引用的外部文件只有iostream,函数(包括引用)一共35行,充分发扬了递归算法写得快的优点。

#include <iostream>

using namespace std;
int getValue(int priority=2) {
    if (priority == 0) {
        int result = 0;
        char c = static_cast<char>(cin.peek());
        if (c == '(') {
            cin.get();
            result = getValue();
            cin.get();
        } else {
            while (c >= '0' and c <= '9') {
                result = result * 10 + c - '0';
                cin.get();
                c = static_cast<char>(cin.peek());
            }
            cout <<result;
        }
        return result;
    } else {
        int result = getValue(priority - 1);
        char op = static_cast<char>(cin.peek());
        while (((op == '+' || op == '-' )&& priority==2)||((op == '*' || op == '/' )&& priority==1)) {
            cin.get();
            int value = getValue(priority - 1);
            if (op == '+') { result += value; }
            else if (op == '-') { result -= value; }
            else if (op == '*') { result *= value; }
            else if (op == '/') { result /= value; }
            cout <<op;
            op = static_cast<char>(cin.peek());
        }
        return result;
    }
}

变量解释

代码中出现的所有变量如下:

  • priority:int 运算优先级,数值约小越先运算,数值越大越先调用
  • isFirstFactor:bool 是否已输出后缀表达式的第一个数
  • result :int 结果暂存
  • c: char 用于存储自输入流读入的一个字符
  • op:char 用于存储计算符
  • value: int 用于存储运算数

实现的大概解释

  1. 传入参数priority=0时,即为计算叶子节点或括号括起来的表达式
  2. 传入参数priority=1时,即为计算乘除法
  3. 传入参数priority=2时,即为计算加减法
  4. 在实际使用时,主干会产生getValue(2)->getValue(1)->getValue(0)的一个递归调用,即自顶向下的递,然后从下至顶的归,是经典的树的递归算法。

测试代码

在声明了函数后,直接使用如下代码即能计算稍后输入的正整数的四则运算中缀表达式。

int main() {
    int result = getValue();
    cout << endl << result << endl;
    return 0;

鬼畜版浓缩重构代码

下面这段代码花了我一晚上,专门为了鬼畜写的,这都能看懂的,真是巨佬.

其实就是在上面的代码重构调整了一下,去除了输出后缀表达式的部分.然后故弄玄虚改了一些代码.

计算表达式的值功能不变,从前往后三个版本逐渐变地可读

短小精干,11行 6个分号:

#include <iostream>

#define a static_cast<char>(std::cin.peek())

#define b static_cast<char>(std::cin.get())

int c(int d = 2){
    int e = (!d) ? 0 : c(d >> 1);
    if (!(a ^ 40) && (!d) && b) e = c() ^ b ^ 41;
    while ((!d) && a >= 48 & a <= 57) e = e * 10 + b - 48;
    while ((d & 1) && !(1974 % a)) e = (b ^ 47) ? e * c(d >> 1) : e / c(d >> 1);
    while ((d & 2) && !(1935 % a)) e = (b ^ 45) ? e + c(d >> 1) : e - c(d >> 1);
    return e;
}

下面这个稍微好理解一点

#include <iostream>

#define a static_cast<char>(std::cin.peek())

#define b static_cast<char>(std::cin.get())

int c(int d = 2) {
    int e = (!d) ? 0 : c(d >> 1);
    if (!(d ^ 40)) {
        b;
        e = c();
        b;
    } else if (!d)while (a >= 48 & a <= 57) e = e * 10 + b - 48;
    else if (d & 1)while (!(1974 % a)) e = (b ^ 47) ? e * c(d >> 1) : e / c(d >> 1);
    else if (d & 2)while (!(1935 % a)) e = (b ^ 45) ? e + c(d >> 1) : e - c(d >> 1);
    return e;
}

如果真的想理解这段鬼畜,下面是鬼畜前的优质代码,比较容易理解

#include <iostream>

#define peek static_cast<char>(std::cin.peek())

#define get static_cast<char>(std::cin.get())

int value(int priorty = 2)
{
    int result = (priorty == 0) ? 0 : value(priorty - 1);
    if (peek == '(')
    {
        get;
        result = value();
        get;
    }
    else if (priorty == 0)
        while (peek >= '0' && peek <= '9')
            result = result * 10 + get - '0';
    else if (priorty == 1)
        while (peek == '*' || peek == '/')
            result = (get == '*') ? result * value(priorty - 1) : result / value(priorty - 1);
    else if (priorty == 2)
        while (peek == '+' || peek == '-')
            result = (get == '+') ? result + value(priorty - 1) : result - value(priorty - 1);
    return result;
}

鬼畜集成到main函数里

# include <iostream>

# define a static_cast<char>(std::cin.peek())

# define b static_cast<char>(std::cin.get())

int main(int c = 1,char** useless = nullptr)
{
    int d = (c >> 2) ? 0 : main(-~c);
    if (!(a ^ 40) && (c >> 2) && b) d = main() ^ b ^ 41;
    while ((c >> 2) && a >= 48 & a <= 57) d = d * 10 + b - 48;
    while ((c & 3) && !(1974 % a)) d = (b ^ 47) ? d * main(-~c) : d / main(-~c);
    while (!(c ^ 2) && !(1935 % a)) d = (b ^ 45) ? d + main(-~c) : d - main(-~c);
    if (!(c >> 1) && a ^ 41) std::cout << d << std::endl;
    return (!(c >> 1) && a ^ 41) ? 0 : d;
}

Licence

  • 2019-4-17 24:00:00前,本文代码保留所有权利,不允许分发,复制或者创造衍生物。
  • 2019-4-17 24:00:00后,使用WTFPL开源。
本文总字数: 3775