一、设计目的

将程序设计语言中的算术表达式转换为用逆波兰表示的形式，并计算逆波兰表示的表达式的值。

二、设计内容

逆波兰表示形式是把运算对象写在前面，把运算符写在后面，用这种方法表示的表达式也称作后缀式。逆波兰表示形式的特点在于运算对象顺序不变，运算符的位置反映运算顺序。采用逆波兰式可以很好的表示简单算术表达式，优点在于易于计算机处理。

1.逆波兰式生成的思想及算法

（1）构造一个运算符栈，栈顶算符的优先级较高；
（2）读入一个用中缀形式表示的简单算术表达式，以“#”结束；
（3）从左至右扫描该表达式，从第一个字符开始，读入每个字符：
①如果该字符是运算数，则分析到该运算数的结束并将该运算数直接输出；
②如果是运算符，则将该算符与栈顶运算符的优先关系进行比较：若优先级高于栈顶运算符，则将该算符入栈，否则将栈顶算符出栈，该算符入栈；

重复上述步骤直至扫描完整个表达式，确定所有字符都得到正确处理，便可将中缀形式的表达式转化为逆波兰形式表示的表达式。

2.逆波兰式的计算方法

（1）构造一个栈，存放运算对象；
（2）读入逆波兰形式的算术表达式；
（3）自左至右扫描该表达式，判断读入的每个字符：
①如果该字符是运算数，则将该字符入栈；
②如果是运算符，若是双目运算符，则弹出栈顶 2 个元素进行该运算，结果入栈；是单目运算符，则弹出栈顶 1 个元素进行该运算，结果入栈；
重复以上过程直至扫描完整个表达式。

三、扩充功能

若输入表达式含有实数，编程实现逆波兰式的生成和计值。

四、算法实现

1.算法流程图

2.程序代码

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <Windows.h>
#include <stdio.h>
#include <ctype.h>
#include <stack>
#include <ctype.h>
#include <map>
using namespace std;
#define INITIAL SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE); // 字体恢复原来的颜色
#define GREEN SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_GREEN);
#define YELLOW SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 0x0e);
#define PURPLE SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 0x0d);
int Sample = 1;             //
int i_all;                  //字符表长度
double ANS = 0;             //结果
stack<double> Num;          //运算数栈
stack<char> Ope;            //运算符栈
string Notation[255];       //字符表
string token;               //中缀表达式
string note;                //数字转存
map<char, int> Opera;       //优先级
void ReversePolishNotation()
{
    PURPLE
    cout << "Sample-" << Sample << endl;
    Sample++;
    while(!Ope.empty()) Ope.pop();
    Ope.push('#');
    i_all = 1;
    note = "";
    for(int i = 0 ; i < token.size() ; i++)
    {
        if (token[i] == ' ' || token[i] == '\t')        //过滤空格和Tab
        {
            continue;
        }
        if(isdigit(token[i]) || token[i] == '.')                 //当前位是数字
        {
            note.push_back(token[i]);
            if(!isdigit(token[i+1]) && token[i+1] != '.')        //下一位既不是数字，也不是小数点
            {
                Notation[i_all] = note;     //将数字转存
                i_all++;                    //中间表长度+1
                //cout << note << endl;
                note = "";                  //Note初始化
            }
        }
        else                                //当前位不是数字
        {
            if(token[i] == '(')             //左括号，入栈
            {
                Ope.push(token[i]);
            }
            else if(token[i] == ')')             //右括号，出栈到匹配上一个左括号
            {
                while(TRUE)
                {
                    if(Ope.top() == '(')
                    {
                        Ope.pop();
                        break;
                    }
                    else
                        Notation[i_all] = Ope.top();
                        Ope.pop();
                        i_all++;
                }
            }
            else                                //其他运算符
            {
                if(Opera[token[i]] > Opera[Ope.top()])      //如果优先级高，入栈
                {
                    Ope.push(token[i]);
                }
                else                                        //否则栈顶运算符出栈，该运算符入栈
                {
                    Notation[i_all] = Ope.top();
                    Ope.pop();
                    i_all++;
                    Ope.push(token[i]);
                }
            }
        }
    }
    while(!Ope.empty())                 //将余下运算符出栈
    {
        Notation[i_all] = Ope.top();
        Ope.pop();
        i_all++;
    }
    GREEN
    for(int i = 1 ; i < i_all -1; i++)
    {
        cout << Notation[i] << " ";
    }
    cout << endl;
    token = "";
}
void Compute()
{
    ANS = 0;
    while(!Num.empty()) Num.pop();
    for(int i = 1 ; i < i_all -1 ; i++)
    {
        if(isdigit(Notation[i][0]))                 //当前元素是一个数
        {
            //cout << "This is  Num: " << Notation[i] << endl;
            Num.push(stold(Notation[i]));           //入栈
        }
        else                                        //运算符，取数计算
        {
            ANS = 0;
            double An, Bn;
            Bn = Num.top();
            Num.pop();
            An = Num.top();
            Num.pop();
            if(Notation[i] == "+")
            {
                ANS = An + Bn;
            }
            else if(Notation[i] == "-")
            {
                ANS = An - Bn;
            }
            else if(Notation[i] == "*")
            {
                ANS = An * Bn;
            }
            else if(Notation[i] == "/")
            {
                ANS = An / Bn;
            }
            //cout << "This is ANS: " << ANS << endl;
            Num.push(ANS);          //计算完成，结果压回栈里
        }
    }
    YELLOW
    cout << "The ans is: " << setprecision(12) << ANS << endl << endl;
}
void Read(FILE *fp)
{
    char ch;
    while (TRUE)
    {
        ch = fgetc(fp);
        if (ch == '\n' || ch == EOF)
        {
            if (token != "")
            {
                ReversePolishNotation();
                Compute();
            }
        }
        else
        {
            token.push_back(ch); // 将读取的字符ch存入token中
        }
        if(ch == EOF)
            break;
    }
}
int main()
{
    Opera['/'] = 2;         //算数优先级排布
    Opera['*'] = 2;
    Opera['-'] = 1;
    Opera['+'] = 1;
    Opera['#'] = 0;
    Opera['('] = 0;
    Opera[')'] = 0;
    string filename; // 文件路径
    FILE *fp;        // 文件指针
    cout << "Please enter the path: ";
    while (true)
    {
        cin >> filename;
        fp = fopen(filename.c_str(), "r");
        if (fp != NULL)
            break;
        else
            cout << "Wrong Path, Please try again" << endl;
    }
    Read(fp);
    fclose(fp);
    INITIAL
    system("pause");
    return 0;
}