一、根据运算符的优先级加括号法

举例：中缀表达式求后缀表达式

a+b*(c-d)-e/f


根据运算符的优先级给表达式加上括号           ((a+(b*(c-d)))-(e/f))
	
  将最外层的符号先提取到对应括号的右侧：（前缀表达式与之相反，是将运算符移动到对应括号的左侧，不再举例）
（（a+（b*（c-d）））（e/f））— ）  //相对整个表达式来讲 这个减号是最外层的运算符
	
（（a（b*（c-d）））+（ef））—  ） //从左向右这个+属于最外层
	
  (（a（b*（c-d）））+（ef）/）— ）//....
	
  (（a（b（c-d））*）+（ef）/）—）//...
	
  (（a（b（cd）-）*）+（ef）/）—）//...
	
abcd-*+ef/-       //最后去掉所有的括号
	
其实也不用管那个是属于最外层的，只要把符号移动到对应的括号右边就行
二、利用栈来求后缀表达式（求前缀表达式也一样，只不过是从右往左遍历中缀表达式，并将每次遇到的操作数或弹出的运算符写在当前操作数或运算符的左侧）



中缀表达式求后缀表达式：

a+b*(c-d)-e/f


从左到右将遇到的运算符入栈，遇到操作数直接将其写下来就行
	
在将运算符入栈的时候先看看是否即将入栈的运算符优先级是否高于栈顶运算符的优先级，如果高则直接入，如果低，那么就进行出栈，直到栈顶的运算符优先级低于即将要入的运算符优先级，将弹出的运算符 跟在刚刚的操作数后面就行。
	
如果入栈的时候运算符是右括号那么就出栈，直到出栈遇到左括号再停止出栈
三、将中缀表达式画成二叉树，然后对其进行前序和后序遍历即可

先从右向左遍历中缀表达式，找到从右到左的第一个优先级最低的运算符来做二叉树的根，确定根之后那么它的左右子树基本确定，然后第二次遍历中缀表达式找第二优先级最低的运算符，然后根据刚刚的大致位置确定第二最低优先级运算符的位置

	

文字：独木
排版：独木
图片：独木
栈与队列
1.括号匹配问题
栈
例题1
例题2-----不匹配例题1
例题3-----不匹配例题2
2. 表达式求值问题
例题
1.中缀表达式转前缀表达式
2.中缀表达式转后缀表达式
实现过程：
3. 递归：
递归产生的问题：
1.括号匹配问题
栈
例题1
算法思想:1)初始一个空栈，顺序读入括号。
若是右括号，则与栈顶元素进行匹配
·若匹配，则弹出栈顶元素并进行下一个元素
·若不匹配，则该序列不合法
3)若是左括号，则压入栈中
4)若全部元素遍历完毕，栈中非空则序列不合法
   解题：1.首先1、2都是左括号，直接进栈
2.第3个括号是右括号‘)’并且和2’(‘匹配，所以弹出当前栈顶元素，如下图
例题2-----不匹配例题1
’
 解题：1.和刚才一样,左括号进栈2.第3个括号是右括号且与当前栈顶左括号2不匹配，所以此题不匹配
例题3-----不匹配例题2
题目：
 解题：1.左括号1、2进栈，如下图2.第三个括号为右括号且与当前栈顶2 左括号匹配，所以弹出此时栈顶2 左括号，然后括号4‘ ]’,与当前栈顶1 左括号’[‘,相匹配，所以弹出此时栈顶1’[‘第5个为左括号进栈，如下图3.栈非空，不合法。
2. 表达式求值问题
前缀表达式:+AB
中缀表达式:A+B
后缀表达式:AB+符号分别在式子的前中后
例题
题目：[(A+B)*C]- [E-F]
1.中缀表达式转前缀表达式
1.最先运算的A+B ,‘+’提前,如下图
2.然后是()*c, 转换前缀就是将*提前 ，如下图
3，E-F, 将‘-’提前。如下图
4.最后一步就是【】-【】，两个中括号相减， 改为前缀就是将减号提前，如下图
[(A+B)*C]- [E-F] 转成下图
2.中缀表达式转后缀表达式
1，式子首先运算A+B,将’+‘后移，如下图：A B +
2，*计算( )*c，转为后缀是将’*‘后移，为()C ,如下图：
3，计算[E-F],将’-’后移，E F - ，如下图
4，计算[ ] -[ ],将‘-’后移 [ ] [ ] - , 如下图
最终：A B + C * E F - -
实现过程：
算法思想:zho数字直接加入后缀表达式
运算符时:
a.若为‘(’，入栈;
b.若为‘)’，则依次把栈中的运算符加入后缀表达式，直到出现’(’，并从栈中删除’(’;
c.若为’+’，‘-’，‘*’，’/‘，
·栈空，入栈;
·栈顶元素为’(’，入栈;
·高于栈顶元素优先级，入栈;
·否则，依次弹出栈顶运算符，直到一个优先级比它低的运算符或‘('为止;
d.遍历完成，若栈非空依次弹出所有元素。
1.都为左括号，入栈(算法思想中情况a)，如下图
2，数字A直接加入表达式
3.加号‘+’，且此时栈顶为左括号，入栈操作，(算法思想中c)如下图
4.数字B直接加入表达式
5.符号‘)’，(算法思想b)依次将此时栈中元素弹出加入后缀表达式直到遇到左括号‘(’，并从栈中删除“(”，如下图，
删除后，栈中只有第一个‘(’
6.符号‘’，(算法思想c)此时栈顶为‘(’ ，直接入栈，如下图
7.减号‘-’，不高于此时栈顶‘’的优先级，弹出栈中元素，直到‘(’,(算法思想c).
8.减号‘-’，此时栈为空，直接入栈(算法思想C)
左括号‘(’，直接入栈
数字E直接加入后缀(算法思想a)
减号‘-’，因为此时栈顶为左括号‘(’，所以减号直接入栈(算法思想C)
数字F直接加入后缀(算法思想a)
9.右括号‘)’，依次弹出栈顶加入到后缀，直到遇到左括号‘(’(算法思想b)。
10.遍历完了，若栈不为空，将栈中数据依次弹出加入到后缀。(算法思想d)
3. 递归：
递归若在一个函数、过程或数据结构的定义中又应用了它自身，则称它为递归定义的，简称递归
int 
递归的精髓在于能否将原始问题转换为属性相同但规模较小的问题
递归产生的问题：
 *在递归调用过程中，系统为每一层的返回点、局部变量、传入实参等开辟了递归工作栈来进行数据存储，递归次数过多容易造成栈溢出。
 *通常情况下递归的效率并不高
***递归转换算法转换为非递归算法，往往需要借助栈来进行
End
1
发现更多精彩
关注公众号

目录

一、中缀表达式转前缀表达式计算机求值算法介绍

二、中缀表达式转前缀表达式计算机求值代码实现

一、中缀表达式转前缀表达式计算机求值算法介绍


1.将中缀表达式转成前缀表达式，具体算法和代码实现可参考我的博客咸鱼学数据结构与算法——中缀表达式转前缀表达式

2.前缀表达式计算机求值，具体算法和代码实现可参考我的博客咸鱼学数据结构和算法——前缀表达式计算机求值


二、中缀表达式转前缀表达式计算机求值代码实现

public class PolandNotationCalculator {

    public static void main(String[] args) {
        String InfixExperssion="(3+4)*5-6";
        Stack<String> numStack =new Stack<String>();
        System.out.println("中缀表达式为:"+InfixExperssion);
        List<String> PrefixExperssion=InfixToPrefix(InfixExperssion);
        System.out.println("前缀表达式为:"+PrefixExperssion);
        PrefixCalculate(PrefixExperssion,numStack);
        System.out.println("最后的结果为:"+numStack.pop());

    }

//    中缀表达式转前缀表达式
 


    public static List<String> InfixToPrefix(String infixExperssion){
//        从右向左扫描
        int index=infixExperssion.length()-1;
//      用来存放前缀表达式
        List<String> resultList=new ArrayList<String>();
//      用来存放运算符
        Stack<String> operStack=new Stack<String>();
//      用来拼接数字，多位数字
        String joint="";
        while (true){
//          当扫描完毕后，退出循环
            if(index<0){
                break;
            }
//            如果扫描到是操作数，直接将结果加入到结果list中
//            如果是多位数的问题已经解决
            if (isNum(infixExperssion.charAt(index))){
//                由于是从右向左扫描，所以拼接要从右侧开始拼接
                joint=infixExperssion.charAt(index)+joint;
//              判断是否越界，如果越界则不需要比较
                if(index>1){
//                    判断下一个字符是否为数字
                    if(!isNum(infixExperssion.charAt(index-1))){
                        resultList.add(joint);
                        joint="";
//                      执行完成后让index加一，不然会陷入死循环
                        index--;

                    }else {
                        index--;
                    }
//              已经是最后一位数了，不需要看下一位了
                }else {
                    resultList.add(joint);
                    joint="";
                    index--;
                }
//          如果是运算符，根据运算符优先级判断运算符是否进入运算符栈
            }else if(isOper(infixExperssion.charAt(index))){
                char oper=infixExperssion.charAt(index);
//              如果为空，则直接加入到运算符中
                if (operStack.empty()){
                    operStack.push(String.valueOf(oper));
                    index--;
//              如果优先级大于运算符栈顶运算符的优先级，将运算符加入到运算符栈中
                }else if(Priority(oper)>Priority(operStack.peek().charAt(0))){
                    operStack.push(String.valueOf(oper));
                    index--;
//              将运算符栈栈顶的运算符加入到List数组中
                }else {
                    resultList.add(operStack.pop());
//                    index++;
                }

//          如果是右括号，将右括号放入运算符栈中
            }else if(infixExperssion.charAt(index)==')'){
                operStack.push(String.valueOf(infixExperssion.charAt(index)));
                index--;
//          根据右括号来去除左括号
            } else if(infixExperssion.charAt(index)=='('){

                while (!operStack.empty()&&!operStack.peek().equals(")")){
                    resultList.add(operStack.pop());
                }
//             丢弃右括号
                operStack.pop();
                index--;
            }
        }
//      将运算符栈中的运算符弹到list中
        while (!operStack.empty()){
            resultList.add(operStack.pop());
        }
//      将结果反转
        Collections.reverse(resultList);
        return resultList;
    }




    public static int Priority(char ch){
        if (ch=='+'||ch=='-'){
            return 1;
        }else if (ch=='*'||ch=='/'){
            return 2;
        }else {
            return 0;
        }
    }

    public static void PrefixCalculate(List<String> PrefixExperssion, Stack<String> numStack){
        //        从右向左扫描
        for (int i=PrefixExperssion.size()-1;i>=0;i--){
           System.out.println(PrefixExperssion.get(i));
            if (isNum(PrefixExperssion.get(i))){
//                System.out.println("测试入栈数据"+PrefixExperssionSplit[i]);
                numStack.push(PrefixExperssion.get(i));
            }else {
//              栈顶数字
                int num1=Integer.valueOf(numStack.pop());
//              次栈顶数字
                int num2=Integer.valueOf(numStack.pop());
                String opr=PrefixExperssion.get(i);
                int res=Calculate(num2,num1,opr);
                numStack.push(String.valueOf(res));
            }

        }


    }


  
    public static boolean isOper(char oper){
        if(oper=='+'||oper=='-'||oper=='*'||oper=='/'){
            return true;
        }else {
            return false;
        }
    }
    public static boolean isNum(char num){
        if(num>=48&&num<=57){
            return true;
        }else {
            return false;
        }
    }

    public static boolean isNum(String str){
        if(str.equals("+")||str.equals("-")||str.equals("*")||str.equals("/")){
            return false;
        }else {
            return true;
        }
    }

    public static int Calculate(int num1,int num2,String opr){
        int res=0;
        switch (opr){
            case "+":
                res=num1+num2;
                break;
            case "-":
                res=num2-num1;
                break;
            case "*":
                res=num1*num2;
                break;
            case "/":
                res=num2/num1;
                break;
            default:
                break;
        }
        return res;
    }

}


 

中缀表达式（中缀记法）
中缀表达式是一种通用的算术或逻辑公式表示方法，操作符以中缀形式处于操作数的中间。中缀表达式是人们常用的算术表示方法。

虽然人的大脑很容易理解与分析中缀表达式，但对计算机来说中缀表达式却是很复杂的，因此计算表达式的值时，通常需要先将中缀表达式转换为前缀或后缀表达式，然后再进行求值。对计算机来说，计算前缀或后缀表达式的值非常简单。

前缀表达式（前缀记法、波兰式）

前缀表达式的运算符位于操作数之前。

前缀表达式的计算机求值：

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。

例如前缀表达式“- × + 3 4 5 6”：

(1) 从右至左扫描，将6、5、4、3压入堆栈；

(2) 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做比较），计算出3+4的值，得7，再将7入栈；

(3) 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈；

(4) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

可以看出，用计算机计算前缀表达式的值是很容易的。

将中缀表达式转换为前缀表达式：

遵循以下步骤：

(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；

(2) 从右至左扫描中缀表达式；

(3) 遇到操作数时，将其压入S2；

(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：

(4-1) 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈；

(4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1；

(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；

(5) 遇到括号时：

(5-1) 如果是右括号“)”，则直接压入S1；

(5-2) 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃；

(6) 重复步骤(2)至(5)，直到表达式的最左边；

(7) 将S1中剩余的运算符依次弹出并压入S2；

(8) 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。
例如，将中缀表达式“1+((2+3)×4)-5”转换为前缀表达式的过程如下：

扫描到的元素
S2(栈底->栈顶)
S1 (栈底->栈顶)
说明
5
5
空
数字，直接入栈
-
5
-
S1为空，运算符直接入栈
)
5
- )
右括号直接入栈
4
5 4
- )
数字直接入栈
×
5 4
- ) ×
S1栈顶是右括号，直接入栈
)
5 4
- ) × )
右括号直接入栈
3
5 4 3
- ) × )
数字
+
5 4 3
- ) × ) +
S1栈顶是右括号，直接入栈
2
5 4 3 2
- ) × ) +
数字
(
5 4 3 2 +
- ) ×
左括号，弹出运算符直至遇到右括号
(
5 4 3 2 + ×
-
同上
+
5 4 3 2 + ×
- +
优先级与-相同，入栈
1
5 4 3 2 + × 1
- +
数字
到达最左端
5 4 3 2 + × 1 + -
空
S1中剩余的运算符

因此结果为“- + 1 × + 2 3 4 5”。
后缀表达式（后缀记法、逆波兰式）

后缀表达式与前缀表达式类似，只是运算符位于操作数之后。

后缀表达式的计算机求值：

与前缀表达式类似，只是顺序是从左至右：

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 op 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。

例如后缀表达式“3 4 + 5 × 6 -”：

(1) 从左至右扫描，将3和4压入堆栈；

(2) 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素，注意与前缀表达式做比较），计算出3+4的值，得7，再将7入栈；

(3) 将5入栈；

(4) 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；

(5) 将6入栈；

(6) 最后是-运算符，计算出35-6的值，即29，由此得出最终结果。

将中缀表达式转换为后缀表达式：

与转换为前缀表达式相似，遵循以下步骤：

(1) 初始化两个栈：运算符栈S1和储存中间结果的栈S2；

(2) 从左至右扫描中缀表达式；

(3) 遇到操作数时，将其压入S2；

(4) 遇到运算符时，比较其与S1栈顶运算符的优先级：

(4-1) 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

(4-2) 否则，若优先级比栈顶运算符的高，也将运算符压入S1（注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）；

(4-3) 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；

(5) 遇到括号时：

(5-1) 如果是左括号“(”，则直接压入S1；

(5-2) 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；

(6) 重复步骤(2)至(5)，直到表达式的最右边；

(7) 将S1中剩余的运算符依次弹出并压入S2；

(8) 依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。

例如，将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下：

扫描到的元素
S2(栈底->栈顶)
S1 (栈底->栈顶)
说明
1
1
空
数字，直接入栈
+
1
+
S1为空，运算符直接入栈
(
1
+ (
左括号，直接入栈
(
1
+ ( (
同上
2
1 2
+ ( (
数字
+
1 2
+ ( ( +
S1栈顶为左括号，运算符直接入栈
3
1 2 3
+ ( ( +
数字
)
1 2 3 +
+ (
右括号，弹出运算符直至遇到左括号
×
1 2 3 +
+ ( ×
S1栈顶为左括号，运算符直接入栈
4
1 2 3 + 4
+ ( ×
数字
)
1 2 3 + 4 ×
+
右括号，弹出运算符直至遇到左括号
-
1 2 3 + 4 × +
-
-与+优先级相同，因此弹出+，再压入-
5
1 2 3 + 4 × + 5
-
数字
到达最右端
1 2 3 + 4 × + 5 -
空
S1中剩余的运算符


因此结果为“1 2 3 + 4 × + 5 -”（注意需要逆序输出）。