中缀表达式转后缀表达式(C++栈实现)

理论参考https://blog.csdn.net/qianyayun19921028/article/details/89228263
中缀表达式就是我们正常使用的那种，例如：a+b*c

后缀表达式就是abc*+；

为什么要有中缀表达式和后缀表达式呢？

因为中缀表达式便于人们的理解与计算，但是后缀表达式更方便计算机的运算（如二叉树、堆栈的方法计算），因此在读取一个中缀表达式后，我们得办法将他转化为后缀表达式。

转化方式有三种：

首先假设我们需要转化的中缀表达式为：

a + b * c + ( d * e + f ) * g

第一种：基于堆栈的算法

从左到右扫描每一个字符。如果扫描到的字符是操作数（如a、b等），就直接输出这些操作数。

如果扫描到的字符是一个操作符，分三种情况：

（1）如果堆栈是空的，直接将操作符存储到堆栈中（push it）

（2）如果该操作符的优先级大于堆栈出口的操作符，就直接将操作符存储到堆栈中（push it）

（3）如果该操作符的优先级低于等于堆栈出口的操作符，就将堆栈出口的操作符导出（pop it）, 直到该操作符的优先级大于堆栈顶端的操作符。将扫描到的操作符导入到堆栈中（push）。

如果遇到的操作符是左括号"（”，就直接将该操作符push到堆栈当中。该操作符只有在遇到右括号“)”的时候移除。这是一个特殊符号该特殊处理。

如果扫描到的操作符是右括号“）”，将堆栈中的操作符导出（pop）到output中输出，直到遇见左括号“（”。将堆栈中的左括号移出堆栈（pop ）。继续扫描下一个字符

如果输入的中缀表达式已经扫描完了，但是堆栈中仍然存在操作符的时候，我们应该讲堆栈中的操作符导出并输入到output 当中。

#include<stdio.h>
#include<iostream>
#include<stack>

using namespace std;

/*
问题描述：
       中缀表达式转后缀表达式
       输入：a+b*c+(d*e+f)*g
       输出：a b c * + d e * f + g * +
*/
stack<char> s;

void changeSuffix(char infix[]) {
    char *p = infix;
    while (*p != '\0') {
        if ('a' <= *p && *p <= 'z') {
            cout << *p;
        }
        if ('+' == *p || '-' == *p) {
            if (s.empty()) {
                s.push(*p);
            }
            else
            {
                while (!s.empty()) {
                    if (s.top() == '(') {
                        break;
                    }
                    cout<<s.top();
                    s.pop();
                }
                s.push(*p);
            }
        }
        if (')' == *p) {
            while ('(' != s.top()) {
                cout << s.top();
                s.pop();
            }
            s.pop();
        }
        if ('*' == *p || '/' == *p || '(' == *p) {
            s.push(*p);
        }

        *p++;
    }
    while (!s.empty()) {    //把栈中剩余的符号弹出
        if (s.top() == '(') 
            s.pop();
        else
        {
            cout << s.top();
            s.pop();
        }
    }
}

int main() {
    cout << "请输入中缀表达式(不能有空格):";
    char infix[50];
    cin >> infix;
    changeSuffix(infix);
    return 0;
}

最后编辑于：2020.07.14 12:11:21