生命不息，奋斗不止

1. 环境准备

1. 下载vagrant和virtualbox，并安装

• vagrant:https://www.vagrantup.com/

• virtualbox:https://www.virtualbox.org/

  注意：vagrant2.2.7发布，本次更新主要添加了对virtualbox6.1.x版本的支持。

2. 虚拟机配置

• 1台master：内存1024MB
• 2台slave：内存512MB

2. 使用vagrant部署虚拟机

1. 安装后vagrant，需提前安装vagrant-hostmanager插件，以便host管理

   1	vagrant plugin install vagrant-hostmanager

2. 从vagrant官网下载ubuntu 16镜像：

   1	vagrant box add ubuntu/xenial64

   也可以使用其他镜像，镜像地址：https://app.vagrantup.com/boxes/search

3. 创建hadoopProject文件夹（可自定），并创建两个文件Vagrantfile和init.sh

   • VagrantFile是vagrant的启动配置文件，
   • init.sh是初始环境的安装脚本

4. 编辑VagrantFile文件， 内容如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

Vagrant.configure("2") do |config|
   config.vm.define :master1, primary: true do |master|
      master.vm.provider "virtualbox" do |v|
         v.customize ["modifyvm", :id, "--name", "hadoop-master1", "--memory", "1024"]
      end
      master.vm.box = "ubuntu/xenial64"
      master.vm.hostname = "hadoop-master1"
      master.vm.network :private_network, ip: "192.168.10.10"
      master.vm.network "forwarded_port", guest: 22, host: 2222, id: "ssh", disabled: "true"
      master.vm.network "forwarded_port", guest: 22, host: 2220
   end

   (1..2).each do |i|
      config.vm.define "slave#{i}" do |node|
         node.vm.box = "ubuntu/xenial64"
         node.vm.hostname = "hadoop-slave#{i}"
         node.vm.network :private_network, ip: "192.168.10.1#{i}"
         node.vm.network "forwarded_port", guest: 22, host: 2222, id: "ssh", disabled: "true"
         node.vm.network "forwarded_port", guest: 22, host: "222#{i}"
         node.vm.provider "virtualbox" do |vb|
            vb.memory = "512"
         end
      end
   end

   #manage hosts file 
   config.hostmanager.enabled = true
   config.hostmanager.manage_host = true
   config.hostmanager.manage_guest = true

   #provision
   config.vm.provision "shell", path: "init.sh", privileged: false
end

从代码可以看到， 我们一共创建了3个虚拟机环境 ，分别是master1, slave1, slave2。并分配好IP地址和内存空间。

注意：在解决多个SSH端口时，需要先禁用默认的ssh转发，再添加自定义转发，才能生效。

5. 在当前目录启动vagrant，会自动依照Vagrantfile配置文件创建虚拟机并配置。

   1	vagrant up

   启动过程中如果有打印如下信息， 一般稍等即可，出错可在VirtulaBox中删除虚拟机及文件重试。

   正常启动后，我们就可以在virtualBox中看到创建的虚拟机。

   正常启动后，我们就可以使用以下命令登录到虚拟机：

   1	vagrant ssh master1

   可以直接按照host名字Ping操作：

   注意：此时默认用户名和密码都是vagrant

   此时，主机仅允许公钥私钥配对SSH链接，建议打开密码认证访问，编辑文件/etc/ssh/sshd_config，修改如下配置为yes：

   1	PasswordAuthentication yes

   重启ssh服务

   1	sudo service ssh restart

   6. 编写provision文件 前面安装vagrant的时候说到，provision的作用是帮助我们进行主机环境的初始化工作，现在我们来编写init.sh，具体内容根据实际情况进行删减。在provision里，我只是安装了linux环境必需的一些组件。

   1 2 3

   sudo apt update # 更新apt sudo apt install openssh-server # 安装SSH sudo apt install openjdk-8-jdk # 安装JAVA

   • 即使因为网络问题导致安装不成功，也可以手动逐个安装。

   编写完后，运行命令进行生效

   1	vagrant provision

3. 配置Hadoop

现在我们有三台机器:

1
2
3

hadoop-master1  192.168.10.10
hadoop-slave1  192.168.10.11
hadoop-slave2  192.168.10.12

Hadoop 集群配置过程:

1. 选定一台机器作为 Master，在所有主机上配置网络映射；
2. 在 Master 主机上配置hadoop用户、安装SSH server、安装Java环境；
3. 在 Master 主机上安装Hadoop，并完成配置；
4. 在其他主机上配置hadoop用户、安装SSH server、安装Java环境；
5. 将 Master 主机上的Hadoop目录复制到其他主机上；
6. 开启、使用 Hadoop。

配置基础环境和SSH互信

所有主机配置hadoop用户、安装SSH server、安装Java环境（前步已执行成功的可以跳过）：

1
2
3

sudo useradd -m hadoop -s /bin/bash     # 创建hadoop用户
sudo passwd hadoop          # 修改hadoop用户密码
sudo adduser hadoop sudo    # 增加hadoop管理员权限

注销并使用 Hadoop 用户登录

1
2
3

sudo apt update         # 更新apt
sudo apt install openssh-server  # 安装SSH
sudo apt install openjdk-8-jdk     # 安装JAVA

设置JAVA_HOME环境变量

1
2
3

sudo nano ~/.bashrc
# 最后面加上
export JAVA_HOME=/usr/lib/jvm/java-8-openjdk-amd64

使 JAVA_HOME 变量生效：

1

source ~/.bashrc    # 使变量设置生效

在 Master 主机上执行：

1
2
3
4
5
6
7

cd ~/
mkdir .ssh
cd ~/.ssh
ssh-keygen -t rsa              # 一直按回车就可以
cat id_rsa.pub >> authorized_keys
scp ~/.ssh/id_rsa.pub hadoop@hadoop-slave1:/home/hadoop/ # 传输公钥到slave1
scp ~/.ssh/id_rsa.pub hadoop@hadoop-slave2:/home/hadoop/ # 传输公钥到slave2

接着在 slave1 节点和slave2节点上保存公钥

1
2
3

cd ~/
mkdir .ssh
cat ~/id_rsa.pub >> ~/.ssh/authorized_keys

如果master主机和slave01、slave02主机的用户名一样，那么在master主机上直接执行如下测试命令，即可让master主机免密码登录slave01、slave02主机。

1

ssh hadoop-slave1

安装Hadoop

先在master主机上做安装Hadoop，暂时不需要在slave1，slave2主机上安装Hadoop。稍后会把master配置好的Hadoop发送给slave1，slave2。 在master主机执行如下操作：

1
2
3
4

tar -zxf ~/hadoop-2.7.7.tar.gz -C /usr/local    # 解压到/usr/local中
cd /usr/local/
sudo mv ./hadoop-2.7.7/ ./hadoop            # 将文件夹名改为hadoop
sudo chown -R hadoop ./hadoop       # 修改文件权限

编辑~/.bashrc文件，末尾添加如下内容：

1
2

export HADOOP_HOME=/usr/local/hadoop
export PATH=$PATH:$HADOOP_HOME/bin:$HADOOP_HOME/sbin

接着让环境变量生效，执行如下代码：

1

source ~/.bashrc

Hadoop集群配置

修改master主机修改Hadoop如下配置文件，这些配置文件都位于/usr/local/hadoop/etc/hadoop目录下。 修改slaves文件，把DataNode的主机名写入该文件，每行一个。

这里让hadoop-master1节点主机仅作为NameNode使用（不包含在slaves文件中）。

1
2

hadoop-slave1
hadoop-slave2

修改core-site.xml

1
2
3
4
5
6
7
8
9
10
11

<configuration>
   <property>
      <name>hadoop.tmp.dir</name>
      <value>/usr/local/hadoop/tmp</value>
      <description>Abase for other temporary directories.</description>
   </property>
   <property>
      <name>fs.defaultFS</name>
      <value>hdfs://hadoop-master1:9000</value>
   </property>
</configuration>

修改hdfs-site.xml：

1
2
3
4
5
6

<configuration>
   <property>
      <name>dfs.replication</name>
      <value>3</value>
   </property>
</configuration>

修改mapred-site.xml（复制并修改文件名mapred-site.xml.template）

1

cp mapred-site.xml.template  mapred-site.xml

1
2
3
4
5
6

<configuration>
   <property>
      <name>mapreduce.framework.name</name>
      <value>yarn</value>
   </property>
</configuration>

修改yarn-site.xml

1
2
3
4
5
6
7
8
9
10
11

<configuration>
   <!-- Site specific YARN configuration properties -->
   <property>
      <name>yarn.nodemanager.aux-services</name>
      <value>mapreduce_shuffle</value>
   </property>
   <property>
      <name>yarn.resourcemanager.hostname</name>
      <value>hadoop-master1</value>
   </property>
</configuration>

配置好后，将 master 上的 /usr/local/Hadoop 文件夹复制到各个节点上。之前有跑过伪分布式模式，建议在切换到集群模式前先删除之前的临时文件。在 master 节点主机上执行：

1
2
3
4
5
6
7

cd /usr/local/
rm -rf /usr/local/hadoop/tmp   # 删除临时文件
rm -rf /usr/local/hadoop/logs/*   # 删除日志文件
tar -zcf ~/hadoop.master.tar.gz ./hadoop   # 打包hadoop
cd ~
scp ./hadoop.master.tar.gz hadoop-slave1:/home/hadoop
scp ./hadoop.master.tar.gz hadoop-slave2:/home/hadoop

在hadoop-slave1，hadoop-slave2节点上执行：

1
2
3

sudo rm -rf /usr/local/hadoop/
sudo tar -zxf ~/hadoop.master.tar.gz -C /usr/local
sudo chown -R hadoop /usr/local/hadoop

启动hadoop集群

在hadoop-master1主机上执行如下命令：

1
2

/usr/local/hadoop/bin/hdfs namenode -format
/usr/local/hadoop/sbin/start-all.sh

运行后，在hadoop-master1，hadoop-slave1，hadoop-slave2运行jps命令，查看：

hadoop-master1运行jps后，如下图（必须有四个进程）：

hadoop-slave1、hadoop-slave2运行jps后，如下图（必须有三个进程）：

4. 在Hadoop上配置Spark

下载Spark

访问Spark官方下载地址，按照如下图下载（不带Hadoop版本）。

下载后，文件移到master虚拟机中，执行解压

1
2
3
4
5

cd ~
sudo tar -zxf spark-2.4.5-bin-without-hadoop.tgz -C /usr/local/
cd /usr/local/
sudo mv ./spark-2.4.5-bin-without-hadoop/ ./spark
sudo chown -R hadoop ./spark

配置环境变量

在hadoop-master1节点主机的终端中执行如下命令：

1

sudo nano ~/.bashrc

在~/.bashrc添加如下配置：

1
2

export SPARK_HOME=/usr/local/spark
export PATH=$PATH:$SPARK_HOME/bin:$SPARK_HOME/sbin

执行如下命令使得配置立即生效：

1

source ~/.bashrc

Spark配置

在Master节点主机上进行如下操作：

• 配置slaves文件

1
2

cd /usr/local/spark/
cp ./conf/slaves.template  ./conf/slaves

slaves文件设置Worker节点。编辑slaves内容，把默认内容localhost替换成slave节点：

1
2

hadoop-slave1
hadoop-slave2

• 配置spark-env.sh文件

1

cp ./conf/spark-env.sh.template ./conf/spark-env.sh

添加如下内容：

1
2
3

export SPARK_DIST_CLASSPATH=$(/usr/local/hadoop/bin/hadoop classpath)
export HADOOP_CONF_DIR=/usr/local/hadoop/etc/hadoop
export SPARK_MASTER_IP=hadoop-master1

SPARK_MASTER_IP 指定 Spark 集群 Master 节点的 IP 地址或主机名。

配置好后，将Master主机上的/usr/local/spark文件夹复制到各个节点上。在Master主机上执行如下命令：

1
2
3
4
5

cd /usr/local/
tar -zcf ~/spark.master.tar.gz ./spark     # 打包spark
cd ~
scp ./spark.master.tar.gz hadoop-slave1:/home/hadoop
scp ./spark.master.tar.gz hadoop-slave2:/home/hadoop

在hadoop-slave1，hadoop-slave2节点上执行：

1
2
3

sudo rm -rf /usr/local/spark/
sudo tar -zxf ~/spark.master.tar.gz -C /usr/local
sudo chown -R hadoop /usr/local/spark

注意：由于我们使用vagrant-hostmanager插件，其会对本地hosts文件修改，导致主机名（host）直接与127.0.1.1绑定，若直接启动Spark master节点，会导致只在127.0.1.1提供服务，其他局域网内slave节点无法访问，因此需要编辑/etc/hosts文件，注释掉：

1

#127.0.1.1      hadoop-master1  hadoop-master1

启动Spark集群

1. 启动Spark集群前，要先启动Hadoop集群。在Master节点主机上运行如下命令：

1

/usr/local/hadoop/sbin/start-all.sh

2. 启动Master节点， 在Master节点主机上运行如下命令：

1

/usr/local/spark/sbin/start-master.sh

在hadoop-master1节点上运行jps命令，可以看到多了Master进程：

3. 启动所有Slave节点，在Master节点主机上运行如下命令：

1

/usr/local/spark/sbin/start-slaves.sh

分别在hadoop-slave1、hadoop-slave2节点上运行jps命令，可以看到多了Worker进程：

在浏览器上查看Spark独立集群管理器的集群信息

spark集群端口：8080

spark-job监控端口：4040

namenode管理端口：50070

yarn端口：8088

在master主机上打开浏览器，访问http://hadoop-master1:8080/，如下图：

关闭Spark集群

1. 关闭Master节点

   1	/usr/local/spark/sbin/stop-master.sh

2. 关闭Worker节点

   1	/usr/local/spark/sbin/stop-slaves.sh

3. 关闭Hadoop集群

   1	/usr/local/hadoop/sbin/stop-all.sh

众所周知，在Python中其实并没有一个严格定义的常量类概念。

目前所采用的常用约定俗成的方式是采用命名全为大写字母的方式来标识别常量。

但实际上这种方式并不能起到防止修改的功能，而只是从语义和可读性上做了区分。

现已有了一种基于__setter__和__delattr__的实现方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

# coding:utf-8
import sys


class _const:
    def __new__(cls, *args, **kw):
        if not hasattr(cls, '_instance'):
            orig = super(_const, cls)
            cls._instance = orig.__new__(cls, *args, **kw)
        return cls._instance

    # 已存在
    class ConstBuiltError(TypeError):
        def __init__(self, name):
            self.msg = "Can't rebind const instance attribute (%s)" % name

        def __str__(self):
            return 'error msg: {}'.format(self.msg)

    # 非全大写错误（可下划线）
    class ConstCaseError(TypeError):
        def __init__(self, name):
            self.msg = 'const name "%s" is not all uppercase' % name
        def __str__(self):
            return 'error msg: {}'.format(self.msg)

        def __repr__(self):
            return self.__str__()

    # 删除错误
    class ConstDelError(TypeError):
        def __init__(self, name):
            self.msg = "Can't delete const instance attribute (%s)" % name

        def __str__(self):
            return 'error msg: {}'.format(self.msg)

        def __repr__(self):
            return self.__str__()

    # 创建时核对是否重复或全大写
    def __setattr__(self, name, value):
        if self.__dict__.__contains__(name):
            raise self.ConstBuiltError(name)
        if not name.isupper():
            raise self.ConstCaseError(name)
        self.__dict__[name] = value

    # 禁止删除
    def __delattr__(self, name):
        if self.__dict__.__contains__(name):
            raise self.ConstDelError(name)
        raise self.ConstDelError(name)


# 实例化一个类
Const = _const()
Const.TEST = 'test'

假设文件保存为constClass使用的时候只要from constClass import Const，便可以直接定义常量了，比如：

1
2
3
4
5
6

from constClass import Const
print(Const.TEST)    # 已有定义
Const.AUTHOR = 'smile'   # 首次定义
Const.AUTHOR = 'smilelc'  # 修改
Const.author = 'smile'          # 小写定义
del Const.AUTHOR                # 删除

1. 已有定义时，如Const.TEST = 'test'，可直接调用；
2. 上面的Const.AUTHOR定义后便不可再更改，因此Const.AUTHOR = ‘smilelc’会抛出ConstBuiltError异常；
3. 而常量名称如果小写，如Const.author ='smile'，也会抛出ConstCaseError异常；
4. 一旦定义完后，若删除，会抛出ConstDelError。

DNS

域名系统（英文：Domain Name System，缩写：DNS）是互联网的一项服务。它作为将域名和IP地址相互映射的一个分布式数据库，能够使人更方便地访问互联网。DNS使用TCP和UDP端口53。当前，对于每一级域名长度的限制是63个字符，域名总长度则不能超过253个字符。

A记录（主机记录）

A（Address）记录是用来指定主机名（或域名）对应的IP地址记录。用户可以将该域名下的网站服务器指向到自己的web server上。

以域名liuchang.men为例，添加A记录：

proxy.liuchang.men是指定域名对应的IP地址47.101.212.137。

A记录同时也可以设置域名的二级域名，如：

使用通配符*泛解析所有 *.proxy.liuchang.men 指向IP地址47.101.212.137。

CNAME记录（别名记录）

CNAME（Canonical Name ）别名记录，允许您将多个名字映射到同一台计算机。通常用于同时提供WWW和MAIL服务的计算机。例如：

若有一台计算机名为smilelc3.github.io（A记录），它能提供WWW服务，而另一台机器名为ym.163.com能提供mail服务，我希望www.liuchang.men能够指向smilelc3.github.io，而mail.liuchang.men能够指向ym.163.com，则记录值如上。

• 注意：记录值留白或使用@符代表使用域名自身作为名称，上表第三条中，@代表liuchang.men指向smilelc3.github.io域名。

AAAA记录（IPv6主机记录）

AAAA 记录是用来指定主机名（或域名）对应的IPv6地址记录。

TXT记录

TXT记录一般是为某条记录设置说明，用来保存域名的附加文本信息，TXT记录的内容按照一定的格式编写，最常用的是SPF（Sender Policy Framework）格式。反垃圾邮件是TXT的应用之一，SPF是跟DNS相关的一项技术，它的内容写在DNS的TXT类型的记录里面。

在命令行下可以使用如下命令来查看域名liuchang.men的TXT记录。

1

nslookup -qt=txt liuchang.men

MX记录

MX记录也叫做邮件路由记录，用户可以将该域名下的邮件服务器指向到自己的mail server上，然后即可自行操控所有的邮箱设置。您只需在线填写您服务器的IP地址，即可将您域名下的邮件全部转到您自己设定相应的邮件服务器上。MX记录的作用是给寄信者指明某个域名的邮件服务器有哪些，SPF格式的TXT记录的作用跟MX记录相反，它向收信者表明，哪些邮件服务器是经过某个域名认可发送邮件的。

DS记录

NS（Name Server）记录是域名服务器记录，用来指定该域名由哪个DNS服务器来进行解析。 您注册域名时，总有默认的DNS服务器，每个注册的域名都是由一个DNS域名服务器来进行解析的，DNS服务器NS记录地址一般以以下的形式出现： ns1.domain.com、ns2.domain.com等。简单的说，NS记录是指定由哪个DNS服务器解析你的域名。

URL记录

将域名指向一个http(s)协议地址，访问域名时，自动跳转至目标地址。

问题要求：给你一个字符串，这个字符串表示一个表达式，这个表达式可能有整数/小数，加减乘除符号和小括号，求这个表达式的值。

三种算术表达式

算术表达式中最常见的表示法形式有 中缀、前缀和 后缀表示法。中缀表示法是书写表达式的常见方式，而前缀和后缀表示法主要用于计算机科学领域。

中缀表示法

中缀表示法是算术表达式的常规表示法。称它为 中缀表示法是因为每个操作符都位于其操作数的中间，这种表示法只适用于操作符恰好对应两个操作数的时候（在操作符是二元操作符如加、减、乘、除以及取模的情况下）。对以中缀表示法书写的表达式进行语法分析时，需要用括号和优先规则排除多义性。

1

(A+B)*C-D/(E+F)

前缀表示法

前缀表示法中，操作符写在操作数的前面。这种表示法经常用于计算机科学，特别是编译器设计方面。为纪念其发明家 ― Jan Lukasiewicz（请参阅参考资料，这种表示法也称 波兰表示法。

1

-*+ABC/D+EF

后缀表示法

在后缀表示法中，操作符位于操作数后面。后缀表示法也称 逆波兰表示法（reverse Polish notation，RPN），因其使表达式求值变得轻松，所以被普遍使用。

1

AB+C*DEF+/-

中缀表达式到后缀表达式的转换

要把表达式从中缀表达式的形式转换成用后缀表示法表示的等价表达式，必须了解操作符的优先级和结合性。 优先级或者说操作符的强度决定求值顺序；优先级高的操作符比优先级低的操作符先求值。 如果所有操作符优先级一样，那么求值顺序就取决于它们的 结合性。操作符的结合性定义了相同优先级操作符组合的顺序（从右至左或从左至右）。

1
2

Left associativity  : A+B+C = (A+B)+C
Right associativity : A^B^C = A^(B^C)

转换过程包括用下面的算法读入中缀表达式的操作数、操作符和括号：

1. 初始化一个空堆栈，将结果字符串变量置空。
2. 从左到右读入中缀表达式，每次一个字符。
3. 如果字符是操作数，将它添加到结果字符串。
4. 如果字符是个操作符，弹出（pop）操作符，直至遇见开括号（opening parenthesis）、优先级较低的操作符或者同一优先级的右结合符号。把这个操作符压入（push）堆栈。
5. 如果字符是个开括号，把它压入堆栈。
6. 如果字符是个闭括号（closing parenthesis），在遇见开括号前，弹出所有操作符，然后把它们添加到结果字符串。
7. 如果到达输入字符串的末尾，弹出所有操作符并添加到结果字符串。

后缀表达式求值

对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中，不需要括号，而且操作符的优先级也不再起作用了。您可以用如下算法对后缀表达式求值：

1. 初始化一个空堆栈
2. 从左到右读入后缀表达式
3. 如果字符是一个操作数，把它压入堆栈。
4. 如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈。如果您不能够弹出两个操作数，后缀表达式的语法就不正确。
5. 到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193

#include <stack>
#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <tuple>
#include <cmath>
#include <sstream>

using namespace std;

//定义栈数据结构体
struct stackData {
    char Operator;
    double Number;
};

inline bool isOperator(char ch) {
    return ch == '+'
           or ch == '-'
           or ch == '*'
           or ch == '/'
           or ch == '^';
}


inline bool isNumber(char ch) {
    return '0' <= ch and ch <= '9' or ch == '.';
}


//优先级判定
inline int priority(char operatorChar) {
    int level = 0;  // level越大，优先级越高
    if (operatorChar == '^') {
        level = 2;
    } else if (operatorChar == '*' or operatorChar == '/') {
        level = 1;
    } else if (operatorChar == '+' or operatorChar == '-') {
        level = 0;
    }
    return level;
}

//获取数字栈顶双数
template<typename T>
tuple<T, T> getTwoNums(stack<T> &nums) {
    auto second = nums.top();
    nums.pop();
    auto first = nums.top();
    nums.pop();
    return {first, second};
}   // return {first, second}

//计算后缀表达式
double postfixCalculate(vector<stackData> &postfix) {
    double first, second;
    stack<double> nums;
    for (const auto &p : postfix) {
        switch (p.Operator) {
            case '*':
                tie(first, second) = getTwoNums(nums);
                nums.push(first * second);
                break;
            case '/':
                tie(first, second) = getTwoNums(nums);
                nums.push(first / second);
                break;
            case '+':
                tie(first, second) = getTwoNums(nums);
                nums.push(first + second);
                break;
            case '-':
                tie(first, second) = getTwoNums(nums);
                nums.push(first - second);
                break;
            case '^':
                tie(first, second) = getTwoNums(nums);
                nums.push(pow(first, second));
                break;
            default:
                nums.push(p.Number);
                break;
        }
    }
    double result = nums.top();
    nums.pop();
    return result;
}

//做分割
vector<stackData> getSeparate(string &infix) {
    vector<stackData> postfix;
    string numStr;  // 单个连续字符的数字
    for (const auto &p : infix) {
        if (isNumber(p)) {
            numStr += p;
        } else if (isOperator(p) or p == '(' or p == ')') {
            if (not numStr.empty()) {
                postfix.emplace_back(stackData{' ', stod(numStr)});
            }
            numStr = "";
            postfix.emplace_back(stackData{p, 0});
        }
    }
    if (not numStr.empty()) {
        postfix.emplace_back(stackData{' ', stod(numStr)});
    }

    //前导缺损+-符号补0
    vector<stackData> newPostfix;
    char preChar = '(';
    for (const auto &p : postfix) {
        if (p.Operator != ' ') {
            if (preChar == '(' and (p.Operator == '-' or p.Operator == '+'))
                newPostfix.emplace_back(stackData{' ', 0});
            preChar = p.Operator;
        } else {
            preChar = ' ';
        }
        newPostfix.emplace_back(p);
    }
    return newPostfix;
}

//表达式输出
string printExpression(vector<stackData> &temp) {
    stringstream ss;
    for (const auto &t: temp) {
        if (t.Operator != ' ') {
            ss << t.Operator;
        } else {
            ss << t.Number;
        }
        ss << ' ';
    }
    return ss.str();
}

//后缀表达式转换
vector<stackData> getPostfixExp(vector<stackData> &infix) {
    stack<char> operator_stack;
    vector<stackData> postfix;
    for (const auto &p: infix) {
        if (isOperator(p.Operator)) {
            while (not operator_stack.empty()
                   and isOperator(operator_stack.top())
                   and priority(operator_stack.top()) >= priority(p.Operator)) {
                postfix.emplace_back(stackData{operator_stack.top(), 0});
                operator_stack.pop();
            }
            operator_stack.push(p.Operator);
        } else if (p.Operator == '(') {
            operator_stack.push(p.Operator);
        } else if (p.Operator == ')') {
            while (operator_stack.top() != '(') {
                postfix.push_back(stackData{operator_stack.top()});
                operator_stack.pop();
            }
            operator_stack.pop();
        } else {
            postfix.push_back(p);
        }

    }
    while (not operator_stack.empty()) {
        postfix.push_back(stackData{operator_stack.top(), 0});
        operator_stack.pop();
    }
    return postfix;
}


int main() {
    cout << "please input string expression: " << endl
         << "example: " << "( 15 / 3 - 1)^2 -(8 + (0.7 - 0.2)*5.41 + 6.8)+1^0.5" << endl;
    string infix;
    // 读取非空行
    while (getline(cin, infix)) {
        infix.erase(infix.find_last_not_of(" \n\r\t") + 1);
        if (not infix.empty()) {
            break;
        }
    }

    vector<stackData> expression = getSeparate(infix);
    cout << "Standard expression: " << printExpression(expression) << endl;
    vector<stackData> postfixExp = getPostfixExp(expression);
    cout << "Postfix expression: " << printExpression(postfixExp) << endl;
    double result = postfixCalculate(postfixExp);
    cout << "Answer: " << setprecision(10) << result;
    return 0;
}