本实验取材于浙江大学《数据结构》，计算后缀表达式，关键在于理解堆栈的工作顺序

//堆栈的应用案例--表达式求值
//表达式求值的基本步数
//1当读入的是一个运算数时，把它被压入栈中；
//2当读入的是一个运算符时，就从堆栈中弹出适当数量的运算数
//对该运算进行计算，计算结果再压回到栈中。
//处理完整个后缀表达时之后，堆栈顶上的元素就是表达时的结果值

下面利用堆栈的顺序存储进行运算！

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#define MAXOP 100//操作数序列可能的最大长度
#define INFINITY 1e9//代表正无穷
#define ERROR -1
typedef double ElementType;//将堆栈的元素类型具体化
//类型依次对应运算符、运算符、字符串结尾

typedef enum{num,opr,end} Type;
typedef int Position;
typedef struct SNode *PtrToStack;

struct SNode{
	ElementType *Data;
	Position Top;
	int MaxSize;
};
typedef PtrToStack Stack;
Stack CreateStack(int MaxSize);//生成空堆栈，其最大长度为Maxsize
int IsFull(Stack S);//判断堆栈S是否已满
int Push(Stack S,ElementType X);//将元素item压入堆栈
int IsEmpty(Stack S);//判断堆栈S是否为空
ElementType Pop(Stack S);//删除并返回栈顶元素
Stack CreateStack(int MaxSize){
	Stack S=(Stack)malloc(sizeof(struct SNode));
	S->Data = (ElementType *)malloc(MaxSize*sizeof(ElementType));
	S->Top = -1;
	S->MaxSize = MaxSize;
	return S;
}
int IsFull(Stack S){
	return (S->Top==S->MaxSize-1);
}

int Push(Stack PtrS,ElementType X)
{
	if(IsFull(PtrS)){
		printf("堆栈满");
		return ERROR;
	}else{
		PtrS->Data[++(PtrS->Top)] = X;
		return PtrS->Data[PtrS->Top];
	}
}
int IsEmpty(Stack S){
	return (S->Top==-1);
}
ElementType Pop(Stack PtrS)
{
	if(PtrS->Top==-1){
		printf("堆栈空");
		return ERROR;
	}else{
		return (PtrS->Data[(PtrS->Top)--]);
	}
}
Type Getop(char *Expr,int *start,char *str)
{
	//从*start开始读入下一个对象(操作数或运算符)，并
	//保存在字符串str中
	int i=0;
	while((str[0]=Expr[(*start)++])==' ');
	while(str[i]!=' ' && str[i]!='\0')
		str[++i]=Expr[(*start)++];
	if(str[i]!='\0')//如果读到输入结尾
		(*start)--;//start指向结束符
	str[i]='\0';//结束一个对象的获取
	if(i==0) return end;//读到了结束
	else if(isdigit(str[0]) || isdigit(str[1]))
		return num;//表示此时str中存的是一个数字
	else    //表示str不是空串，又不是数字
		return opr; //表示此时str中存的是一个运算符
		
	
}
ElementType PostfixExp(char *Expr)
{
	Stack S;
	Type T;
	ElementType Op1,Op2;
	char str[MAXOP];
	int start=0;
	//申请一个新堆栈
	S=CreateStack(MAXOP);
	Op1 = Op2=0;
	while((T=Getop(Expr,&start,str))!= end){
		//当为读到输入结束时
		if(T==num)
			Push(S,atof(str));
		else{
			if(!IsEmpty(S)) Op2 = Pop(S);
			else Op2 = INFINITY;
			if(!IsEmpty(S)) Op1 = Pop(S);
			else Op2 = INFINITY;
			switch(str[0]){
				case '+':Push(S,Op1+Op2);break;
				case '*':Push(S,Op1*Op2);break;
				case '-':Push(S,Op1-Op2);break;
				case '/':
					if(Op2 != 0.0)
						Push(S,Op1/Op2);
					else{
						printf("falut div is zero\n");
						Op2 = INFINITY;
					}
					break;
				default:
					printf("fault unknown fault%s\n",str);
					Op2 = INFINITY;
					break;
			}
			if(Op2>=INFINITY) break;
		}
	}
	if(Op2<INFINITY)
		if(!IsEmpty(S))
			Op2=Pop(S);
		else
			Op2 = INFINITY;
		free(S);
		return Op2;
}
int main()
{
	char Expr[MAXOP];
	ElementType f;
	gets(Expr);
	f=PostfixExp(Expr);
	if(f<INFINITY)
		printf("%.4f\n",f);
	else
		printf("function is fault\n");
	return 0;
}

一、什么是中缀表达式，后缀表达式

二、中缀表达式转后缀表达式

例题：

        中缀表达式：(10+20/2*3)/2+8                 转换为对应的后缀为

        后缀表达式：10 20 2 / 3 * + 2 / 8 +

解题思路：

（1）观察两表达式；后缀明显没有“（）”这两个符号，其次与中缀相比数字的顺组没有变化，运

算符的顺序发生改变。

（2）找对应的数据结构知识，有顺序且对存储的数据类型，没有要求因此可以利用ArrayList进行

数据的存储；同时运算的顺序发生明显改变与其运算符的优先级有关，所以我们可以通过

ArrayStack利用其的进出栈特性，改变其顺序。

实现过程：

（1）创建一个栈和一个线性表

（2）将中缀表达式定义为一个字符串，通过给运算符和（）两端加上空格，在利用split(“ ”)方法

将字符串转换为String[];

（3）遍历String[]，数组元素为数字直接进入线性表；数组元素为运算符和()，先进栈；

a.元素进栈时首先获取栈顶元素优先级，如果该元素的优先级大于等于栈顶元素，栈顶元素弹栈并

存入线性表；

b.如果该元素为“（”直接进栈；

c.如果栈内为空或者栈顶元素为“（”则直接进栈；

d.如果元素为“）”栈中元素弹栈并存入线性表直到栈顶元素为“（”；

注意：“（）”不进入线性表中；具体进出栈代码中有详细体现及说明；

（4）遍历线性表并进行元素的拼接，输出拼接的结果

代码实现：

package p2.线性结构;
//中缀表达式转后缀表达式
public class InfixToSuffix {
    public static void main(String[] args) {
        String expression = "(10+20/2*3)/2+8";
        expression = infixToSuffix(expression);
        System.out.println(expression);
    }
    static String infixToSuffix(String expression) {
        //操作符的栈
        ArrayStack<String> opStack = new ArrayStack<>();
        //后缀表达式的线性表
        ArrayList<String> suffixList = new ArrayList<>();

        //格式化表达式
        expression = insertBlanks(expression);
        String[] tokens = expression.split(" ");
        for (String token : tokens) {
            //过滤空串
            if (token.length() == 0) {
                continue;
            }
            //判断操作符+ - * /
            if (isOperator(token)) {
                /*
                什么时候操作符进栈？
                1.如果栈为空
                2.如果栈顶是 (
                3.如果栈顶是操作符，且优先级比当前token小

                什么时候需要将栈顶操作符出栈？
                1.栈顶操作符的优先级 >= 当前token
                */
                while (true) {
                    if (opStack.isEmpty() || opStack.peek().equals("(") || priority(opStack.peek()) < priority(token)) {
                        opStack.push(token);
                        break;
                    }
                    suffixList.add(opStack.pop());
                }
            } else if (token.equals("(")) {
                opStack.push(token);
            } else if (token.equals(")")) {
                while (!opStack.peek().equals("(")) {
                    suffixList.add(opStack.pop());
                }
                opStack.pop();
            } else if (isNumber(token)) {
                suffixList.add(token);
            } else {
                throw new IllegalArgumentException("wrong char :" + expression);
            }
        }
        while (!opStack.isEmpty()) {
            suffixList.add(opStack.pop());
        }
        //将数字元素和操作符元素进行拼接
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < suffixList.size(); i++) {
            sb.append(suffixList.get(i));
            sb.append(' ');
        }
        return sb.toString();
    }

    private static int priority(String token) {
        if (token.equals("+") || token.equals("-")) {
            return 0;
        }
        if (token.equals("*") || token.equals("/")) {
            return 1;
        }
        return -1;
    }

    private static boolean isNumber(String token) {

        return token.matches("\\d+");
    }

    private static boolean isOperator(String token) {
        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");
    }

    //对原表达式进行格式化处理 给所有的非数字字符两边添加空格
    private static String insertBlanks(String expression) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);
            if (c == '(' || c == ')' || c == '+' || c == '-' || c == '*' || c == '/') {
                sb.append(' ');
                sb.append(c);
                sb.append(' ');
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

输出结果；

 输出结果与开始的预期结果一致；因此代码成功实现转换；

后缀表达式的计算结合博客：

后缀表达式求值_s逐梦少年的博客-CSDN博客

一、中缀表达式转后缀表达式算法思想：

（1）从左向右开始扫描中缀表达式。
（2）遇到数字时，加入后缀表达式。
（3）遇到运算符时：
  a.若为 '('，入栈；
  b.若为 ')'，则依次把栈中的运算符加入后缀表达式，直到出现'('，从栈中删除'('；
  c.若为除括号外的其他运算符，当其优先级高于除'('外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或遇到了一个左括号为止。
（4）当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。

二、中缀表达式转后缀表达式举例：

三、代码实现（java）

package com.hrbeu.datastructure;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author haiYang
 * @create 2021-12-20 18:56
 */
public class PolandNotation {

    public static void main(String[] args) {
        List<String> strings = toInfixExpressionList("1+((2+3)*4)-5");
        System.out.println(strings);

        Stack<String> s1 = new Stack<>//用于处理操作符
        ArrayList<String> list = new ArrayList<>();//用于存储后缀表达式
        for (int i = 0; i < strings.size(); i++) {
        	//若为除括号外的其他运算符，当其优先级高于除'('外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或遇到了一个左括号为止。
            if("+".equals(strings.get(i)) ||"-".equals(strings.get(i))||"*".equals(strings.get(i))||"/".equals(strings.get(i))){
                while(s1.size()!=0 &&priority(strings.get(i))<=priority(s1.peek())){

                    list.add(s1.pop());
                }
                s1.push(strings.get(i));

		
            }else if("(".equals(strings.get(i))){//若为'('，入栈
                s1.push(strings.get(i));
            }else if(")".equals(strings.get(i))){//若为')'，则依次把栈中的运算符加入后缀表达式，直到出现'('，从栈中删除'('
                while(!("(".equals(s1.peek()))){
                    list.add(s1.pop());
                }
                s1.pop();
            }else{
                list.add(strings.get(i));
            }
        }
        while(!s1.empty()){
            list.add(s1.pop());
        }
        System.out.println(list);

    }

	//将字符串转化为列表
    public static List<String> toInfixExpressionList(String s) {
        ArrayList<String> list = new ArrayList<>();
        int i = 0;
        String str;
        char c;
        while (i < s.length()) {
        	//如果不是数字直接加入列表
            if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                list.add(""+c);
                i++;
            }else{
            	//如果是数字，将数字拼接并加入列表
                str = "";
                while(i<s.length()&&(c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57){
                    str = str + c;
                    i++;
                }
                list.add(str);
            }
        }
        return list;
    }
    //优先级判断
    public static int priority(String s){
        if ("*".equals(s) ||"/".equals(s)){
            return 2;
        }else if("+".equals(s) ||"-".equals(s)){
            return 1;
        }else{
            return 0;
        }
    }
}