[数据结构与算法]数据结构-3.3 堆栈应用：表达式求值-程序示例

3.3 堆栈应用：表达式求值

中缀表达式转化为后缀表达式

基本原则：从头到尾读取中缀表达式的每个对象，对不同对象按不同的情况处理

1. 运算数：直接输出
2. 左括号：压入堆栈
3. 右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）
4. 运算符：
   • 优先级 > 栈顶运算符，则把它压栈
   • 优先级 <= 栈顶运算符，则将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符的优先级 > 栈顶运算符的优先级为止，然后将该运算符压栈；
5. 若各个对象处理完毕，则把堆栈中存留的运算符一并输出

$ Main.cpp文件:
#include <iostream>
#include "Stack.h"
using namespace std;

bool ComparePriority(char a, char b) {  //比较运算符优先级
    if ((a == '*' || a == '/') && (b == '+' || b == '-'))
        return true;
    else if (b == '(') return true;
    else return false;
}

int main() {
    Stack<char> s;
    string str;
    char c;
    cout << "请输入中缀表达式: " << endl;
    cin >> str;
    for (size_t i = 0; i < str.size(); i++)  //处理中缀表达式字符串的每一个字符
    {
        if ((str[i] >= '0' && str[i] <= '9') || str[i] == '.') //运算数直接输出
            cout << str[i];
        else if (str[i] == '(') //左括号'('压入堆栈
            s.Push(str[i]);
        else if (str[i] == ')') {  //将栈顶的运算符弹出并输出，直到遇到左括号
            while (true) {
                s.Pop(c);
                if (c != '(') cout << c;
                else break;
            }
        }
        else if (str[i] == '*' || str[i] == '/' || str[i] == '+' || str[i] == '-')
        {
        	//优先级<=栈顶运算符，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到优先级>它
            while (!s.StackEmpty() && !ComparePriority(str[i], s.GetTop()))
            {  
                s.Pop(c);
                cout << c;
            }
            s.Push(str[i]);  //优先级大于栈顶运算符优先级，入栈
        }
    }
    while (!s.StackEmpty()) { //各个字符处理完毕后，把堆栈中存留的运算符一并输出
        s.Pop(c);
        cout << c;
    }
    return 0;
}

测试输入1： 2*(9+6/3-5)+4
运行结果1： 2963/+5-*4+
测试输入2： 1+2-3+4
运行结果2： 12+3-4+
测试输入3： (1+2)*3/4-5
运行结果3： 12+3*4/5-

$ Stack.h文件
#include <iostream>
#include <malloc.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

template<class T>
class Stack
{
private:
	T* top;  // 栈顶指针 
	T* base; // 栈底指针
	int stacksize; // 栈容量
	int length;  // 栈中元素个数
public:
	Stack();
	~Stack();
	bool StackEmpty();  // 判断是否栈空
	int StackLength();  // 取栈长度
	T GetTop();  // 取栈顶元素
	bool Push(T e);  // 入栈
	bool Pop(T &e);  // 出栈（保留出栈元素）
};

template<class T>
inline Stack<T>::Stack()
{
	base = (T*)malloc(STACK_INIT_SIZE * sizeof(T));
	if (!base) exit(-1);
	top = base;
	stacksize = STACK_INIT_SIZE;
	length = 0;
}

template<class T>
inline Stack<T>::~Stack()
{
	free(base);
	base = NULL;
	top = NULL;
}

template<class T>
inline bool Stack<T>::StackEmpty()
{
	return (top == base);
	// 栈空返回true，栈非空返回false
}

template<class T>
inline int Stack<T>::StackLength()
{
	return length;
}

template<class T>
inline T Stack<T>::GetTop()
{
	if (StackEmpty()) exit(-1);
	return *(top - 1);
}

template<class T>
inline bool Stack<T>::Push(T e)
{
	if (top - base >= stacksize)
	{
		T* tmp;
		tmp = (T*)realloc( base, (stacksize + STACKINCREMENT) * sizeof(T) );
		if (tmp != NULL) base = tmp;  // 成功重新分配后替换原指针
		top = base + stacksize;
		stacksize += STACKINCREMENT;
	}
	*top++ = e;
	length++;
	return true;
}

template<class T>
inline bool Stack<T>::Pop(T& e)
{
	if (StackEmpty()) return false;
	e = *(top - 1);
	top--;
	length--;
	return true;
}