4.4.reverse-创新互联

问题描述

中缀表达式就是我们通常所书写的数学表达式，后缀表达式也称为逆波兰表达式，在编译程序对我们书写的程序中的表达式进行语法检查时，往往就可以通过逆波兰表达式进行。我们所要设计并实现的程序就是将中缀表示的算术表达式转换成后缀表示，例如，将中缀表达式

创新互联公司网站建设提供从项目策划、软件开发，软件安全维护、网站优化(SEO)、网站分析、效果评估等整套的建站服务，主营业务为成都网站设计、成都网站建设，app软件定制开发以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。创新互联公司深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

(A 一 (B*C 十 D)*E) ／ (F 十 G )

转换为后缀表示为：

ABC*D十E*--FG十／

注意：为了简化编程实现，假定变量名均为单个字母，运算符只有＋，－，＊，／ 和＾（指数运算），可以处理圆括号（），并假定输入的算术表达式正确。

要求：使用栈数据结构实现 ，输入的中缀表达式以＃号结束

输入

整数N。表示下面有N个中缀表达式

N个由单个字母和运算符构成的表达式

输出

N个后缀表达式。

解题思路

该题是典型的用到栈的一种情况，同时也体现了栈在处理运算符这类优先级等问题方面拥有的特殊功效。思路是遇到字母就直接输出；遇到符号在进栈处理，处理方式如下：

1）如果栈为空，或遇到的元素是'('，直接入栈；

2）如果遇到的元素是')'，将栈中'('以上的全部元素弹出并输出，'('也弹出；

3）如果遇到其他操作符，将栈中比该操作符运算优先级更高的元素都弹出并输出，直到栈为空、或者遇到'('、或者遇到更低优先级的符号；

（这里可以吧左括号在栈中的优先级设置为最低）

4）如果读到输入的末尾，栈中元素依次弹出并输出。

在这个规则中我们需要提炼一些细节，以便于写出简洁和正确的代码。比如：栈为空特别容易引起RE，这个需要就情况分析是否需要检验空栈；还有优先级判断也可以写成一个函数，传入一个符号，返回一个int（代表其优先级）。（然而题主最开始很笨，是挨个判断的）

贴源代码

就用一个简单的代码啦，优先级可以简化。（懒中……

#include#includeusing namespace std;

int main() {
    int N;
    cin >>N;
    getchar();
    stacksig;
    char c;
    while (N--) {
        while (1) {
            cin.get(c);

            if ('#' == c) {
                getchar();
                while (!sig.empty()) {
                    cout<< sig.top();
                    sig.pop();
                }
                cout<< endl;
                break;
            }
            else if ((c >= 'A' && c<= 'Z') || (c >= 'a' && c<= 'z')) {
                cout<< c;
            }
            //运算符:
            else {
                if (sig.empty()) sig.push(c);

                else {
                    if (')' == c) {
                        while (sig.top() != '(') {
                            cout<< sig.top();
                            sig.pop();
                        }
                        sig.pop();//'('
                    }
                    else if ('(' == c)
                        sig.push(c);

                    else if ('^' == c)
                        sig.push(c);//'^'必然入栈

                    else if ('*' == c || '/' == c) {
                        while (!sig.empty() && '+' != sig.top() && '-' != sig.top() && '(' != sig.top()) {
                            if ('*' == sig.top() || '/' == sig.top()) {
                                cout<< sig.top();
                                sig.pop();
                            }
                            else if ('^' == sig.top()) {
                                while (!sig.empty() && '^' == sig.top()) {//注意这里用while是因为可能有连续的'^'('^'运算顺序是从右到左)
                                    cout<< sig.top();
                                    sig.pop();
                                }
                            }
                        }
                        sig.push(c);
                    }

                    else {
                        while (!sig.empty() && '(' != sig.top()) {
                            cout<< sig.top();
                            sig.pop();
                        }
                        sig.push(c);
                    }
                }
            }
        }
    }
    return 0;
}

---

——2023.1.15

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文题目：4.4.reverse-创新互联
文章来源：http://cxhlcq.com/article/gsiho.html