精华内容
下载资源
问答
  • 前缀中缀后缀表达式(逆波兰计算器)及转换

    前缀表达式(波兰表达式)

    前缀表达式分析与介绍

    1. 前缀表达式又称为波兰式,前缀表达式的运算符位于操作数之前
    2. 举例说明:(3+4)*5-6对应的前缀表达式就是 - * + 3 4 5 6

    前缀表达式的计算机求值
    从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对他们做相应的计算(栈顶元素和次顶元素),并将结果入栈;重复上述过程直达表达式最左端,最后运算的得出的值即为表达式的结果

    思路分析

    例如(3+4)*5-6对应的前缀表达式就是 - * + 3 4 5 6,针对前缀表达hi求值步骤如下:

    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. 中缀表达式就是最常见的运算表达式如:(3+4)*5-6
    2. 中缀表达式的求值是我们人最熟悉的,但是对计算机来说却不好操作(参考:【Java数据结构与算法】栈及经典应用),因此,在计算结果时,往往将中缀表达式转成其它的表达式来操作(一般转成后缀表达式

    后缀表达式(逆波兰表达式)

    后缀表达式分析与介绍

    1. 后缀表达式又称为逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后
    2. 举例说明:(3+4)*5-6对应的后缀表达式就是3 4 + 5 * 6 -
    3. 再比如:
    正常的表达式 逆波兰表达式
    a + b a b +
    a + (b - c) a b c - +
    a + (b - c) * d a b c - d * +
    a + d * (b - c) a d b c - * +
    a = 1 + 3 a 1 3 + =

    后缀表达式的计算机求值
    从左到右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素和栈顶元素),并将结果入栈;复上述过程直达表达式最左端,最后运算的得出的值即为表达式的结果

    思路分析逆波兰计算器

    例如(3+4)*5-6对应的前缀表达式就是3 4 + 5 * 6 -,针对后缀表达式求值步骤如下:

    1. 从左到右扫描,将3和4压入堆栈;
    2. 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈;
    3. 将5入栈;
    4. 接下来是运算符,因此弹出5和7,计算出75=35,将35入栈;
    5. 最后是-运算符,计算出35-6的值,即29,由此得出最终结果;

    代码实现逆波兰计算器

    package DataType;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public class PolandNotation {
        public static void main(String[] args){
            //先定义一个逆波兰表达式
            //(3+4)*5-6 =>3 4 + 5 * 6 -
            //说明为了方便,逆波兰表达式的数字和符号使用空格隔开
            String suffixExpression = "3 4 + 5 * 6 -";
            //思路
            //1.先将"3 4 + 5 * 6 -"放到Array List种
            //2.将Array list传递给一个方法,遍历Array list配合栈完成计算
            List<String> rpnList = getListString(suffixExpression);
            System.out.println("rpnList=" + rpnList);
            int res = calculate(rpnList);
            System.out.println("计算的结果是=" + res);
        }
        //将一个逆波兰表达式,依次将数据和运算符放入Array list中
        public static List<String> getListString(String suffixExpression){
            //将suffixExpression分割
            String[] split = suffixExpression.split(" ");
            List<String> list = new ArrayList<String>();
            for (String ele : split){
                list.add(ele);
            }
            return list;
        }
        //完成对逆波兰表达式的运算
        /*
        1.从左到右扫描,将3和4压入堆栈
        2.遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈
        3.将5入栈
        4.接下来是*运算符,因此弹出5和7,计算出7*5=35,将35入栈
        5.最后是-运算符,计算出35-6的值,即29,由此得出最终结果
         */
        public static int calculate(List<String> ls){
            //创建栈,只需要一个栈
            Stack<String> stack = new Stack<String>();
            //遍历ls
            for (String item : ls){
                //这里使用正则表达式来取出数
                if (item.matches("\\d+")){//匹配的是多位数
                    //入栈
                    stack.push(item);
                }else {
                    //pop出两个数,并运算,再入栈
                    int num2 = Integer.parseInt(stack.pop());
                    int num1 = Integer.parseInt(stack.pop());
                    int res = 0;
                    if (item.equals("+")){
                        res = num1 + num2;
                    }else if (item.equals("-")){
                        res = num1 - num2;
                    }else if (item.equals("*")){
                        res = num1 * num2;
                    }else if (item.equals("-")){
                        res = num1 / num2;
                    }else {
                        throw  new RuntimeException("运算符有误~~");
                    }
                    //把res入栈
                    stack.push(res + "");
                }
            }
            //最后留在stack中的结果就是答案
            return Integer.parseInt(stack.pop());
        }
    }
    

    这就是后缀表达式的运算过程,但如果我们只知道中缀表达式不想进行人工转化应该怎么计算呢?

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

    可以看到,后缀表达式适合计算式进行运算,但是人却不太容易写出,尤其是表达式很长的情况,因此在开发中,我们需要将中缀表达式转化成后缀表达式

    思路分析

    中缀表达式转后缀表达式的思路步骤分析:

    1. 初始化两个栈:运算符栈s1和储存中间结果的栈s2;
    2. 从左至右扫描中缀表达式;
    3. 遇到操作数时,将其压入s2;
    4. 遇到运算符时,比较其与s1栈顶运算符的优先级:
      1. 如果s1为空,或栈顶运算符为左括号"(",则直接将此压入运算符入栈;
      2. 否则,若优先级比栈顶运算符高,也将运算符压入s1;
      3. 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到(4-1)与s1中新的栈顶运算符相比较。
    5. 遇到括号时:
      1. 如果是左括号,则直接压入s1;
      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中剩余的运算符

    代码实现

    package DataType;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public class PostfixExpression
    {
        public static void main(String[] args) {
            //完成将一个中缀表达式转成后缀表达式
            //1.因为直接对字符串进行操作不方便,因此先将中缀表达式字符串转成中缀表达式对应的list
            //2.将得到的中缀表达式对应的list转成后缀表达式对应的list
            //即Array list [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] =>Array list后缀表达式
            String expression = "1+((2+3)*4)-5";
            List<String> infixExpressionList = toInfixExpressionList(expression);
            System.out.println("中缀表达式对应的list=" + infixExpressionList);
            List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
            System.out.println("后缀表达式对应的list=" + suffixExpreesionList);
        }
        //即Array list [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] =>Array list后缀表达式
        //方法:将得到的中缀表达式对应的list转成后缀表达式对应的list
        public static List<String> parseSuffixExpreesionList(List<String> ls){
            //定义两个栈
            Stack<String> s1 = new Stack<String>();//符号栈
            //因为s2这个栈,在整个过程中,没有pop操作,而且还得逆序输出,很麻烦,索引就不用栈了,直接使用list
            List<String> s2 = new ArrayList<String>();//存储中间结果的lists2
            //遍历ls
            for (String item : ls){
                //如果是一个数就加入到s2
                if (item.matches("\\d+")){
                    s2.add(item);
                }else if (item.equals("(")){
                    s1.push(item);
                }else if(item.equals(")")){
                    //如果是右括号,则依次弹出s1栈顶的运算符,并压入s2,直到遇到左括号为止,此时将这一对括号丢弃
                    while (!s1.peek().equals("(")){
                        s2.add((s1.pop()));
                    }
                    s1.pop();//!!!!!!!!将小括号删除
                }else {
                    //当item的优先级小于等于s1栈顶运算符的优先级,将s1栈顶的运算符弹出并加入到s2中,再次转到(4-1)与s1中新的栈顶运算符相比较。
                    //问题:缺少比较优先级高低的方法
                    while (s1.size()!=0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)){
                        s2.add(s1.pop());
                    }
                    //还需要将item压入栈
                    s1.push(item);
                }
            }
            //将s1中剩余的运算符依次弹出并且压入s2
            while (s1.size() != 0){
                s2.add(s1.pop());
            }
            return s2;//因为存放的是list,所以正常输出就行了
        }
        //方法:因为直接对字符串进行操作不方便,因此先将中缀表达式字符串转成中缀表达式对应的list
        public static List<String> toInfixExpressionList(String s){
            //定义一个list存放中缀表达式对应的内容
            List<String> ls = new ArrayList<String>();
            int i = 0;//这是个指针,用于遍历中缀表达式字符串
            String str;//对多位数的拼接
            char c;//每遍历到一个字符,就放入到c
            do {
                //如果c是一个非数字,需要加入到ls中
                if ((c=s.charAt(i)) < 48 || (c=s.charAt(i)) >57){
                    ls.add("" + c);
                    i ++;//i需要后移
                }else {//如果是一个数,需要考虑多位数的问题
                    str = "";//先将str 置成""
                    while (i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57){
                        str += c;//拼接
                        i ++;
                    }
                    ls.add(str);
                }
            }while (i < s.length());
            return ls;//返回
        }
    }
    //编写一个类Operation,可以返回一个运算符对应的优先级
    class Operation{
        private static int ADD = 1;
        private static int SUB = 1;
        private static int MUL = 1;
        private static int DIV = 1;
        //写一个方法返回对应的优先级
        public static int getValue(String operation){
            int result = 0;
            switch (operation){
                case "+":
                    result = ADD;
                    break;
                case "-":
                    result = SUB;
                    break;
                case "*":
                    result = MUL;
                    break;
                case "/":
                    result = DIV;
                    break;
                default:
                    System.out.println("不存在该运算符~");
                    break;
            }
            return result;
        }
    }
    

    毕竟编程我是初学者,难免有理解错误的地方,希望大家看完之后,发现错误可以评论出来,谢谢大家

    展开全文
  • (1)前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前 (2)如:(3+4)× 5-6对应的前缀表达式是 - × + 3 4 5 6 前缀表达式的计算机求值: 从右至左扫描表达式,遇到数字时将数字压入堆栈,遇到运算时,...

    栈的三种表达式:
    前缀表达式(波兰表达式)
    (1)前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前
    (2)如:(3+4)× 5-6对应的前缀表达式是 - × + 3 4 5 6
    前缀表达式的计算机求值:
    从右至左扫描表达式,遇到数字时将数字压入堆栈,遇到运算时,弹出栈顶的两个数,用运算符对它们作相应的计算(栈顶元素和次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得到的值即为表达式的结果。

    针对前缀表达式求值步骤如下:
    (1)从右至左扫描,将 6 5 4 3压入堆栈
    (2)遇到 + 运算符,因此弹出3 和4(3为栈顶元素,4为次顶元素),计算出3 + 4的值,得7,再将7入栈
    (3)接下来是 × 运算符,因此弹出7和5,计算出35,将35入栈
    (4)最后是 - 运算符,计算出35 - 6,即29,由此得出最终结果

    中缀表达式
    最常见的运算表达式,如(3+4)×5-6
    计算机不好操作,常使用中缀表达式转成其它表达式来操作

    后缀表达式
    又称逆波兰表达式,与前缀表达式相似,只是运算符位于操作数之后
    比如:(3 + 4) × 5 - 6 对应的后缀表达式为 3 4 + 5 × 6 -
    后缀表达式的计算机求值:
    从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素和栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。

    例如:(3 + 4) × 5 - 6 针对后缀表达式 3 4 + 5 × 6 -的求值步骤如下:
    (1)从左至右扫描,将3和4压入堆栈
    (2)遇到 + 运算符,弹出4 和 3 (4为栈顶元素,3为次顶元素),计算出3 + 4的值,得7,再将7入栈
    (3)将 5 入栈
    (4)接下来是 × 运算符,因此弹出5 和 7,计算出35,将其入栈
    (5)将 6 入栈
    (7)最后是 - 运算符,计算出35 - 6,得到最后结果29

    逆波兰表达式实现逆波兰计算器:
    任务:
    (1)输入一个逆波兰表达式,使用栈(Stack)计算其结果
    (2)支持小括号和多位数整数
    (3)思路分析
    (4)代码完成

    public class PolandNotation{
    	public static void main(String[] args){
    		//TODO Auto-generated mathod stub
    		//先定义一个逆波兰表达式
    		// (3 + 4)× 5 - 6 ==> 3 4 + 5 × 6 -
    		//为了方便,逆波兰表达式的数字和符号使用空格隔开
    		String suffixExpression = "3 4 + 5 × 6 -";
    		//思路:
    		//1、先将 "3 4 + 5 × 6 -"放到ArrayList中
    		//2、将ArrayList传递给一个方法,遍历ArrayList,配合栈完成计算
    		
    		List<String> rpnList = getListString(suffixExpression);
    		System.out.println("rpnList="+rpnList);
    
    		int res = calculate(list);
    		System.out.println("计算的结果是=" + res);
    	}
    	//将一个逆波兰表达式,依次将数据和运算符放入到ArayList中
    	public static List<String> getListString(String suffixExpression){
    		//将suffixExpression分割
    		String[] split = suffixExpression.split(" ");
    		List<String> list = new ArrayList<String>();
    		for(String ele:split){
    			list.add(ele);
    		}
    		return list;
    	} 
    	//完成对逆波兰表达式的运算
    	/**
    	(1)从左至右扫描,将3和4压入堆栈
    	(2)遇到 + 运算符,弹出4 和 3 (4为栈顶元素,3为次顶元素),计算出3 + 4的值,得7,再将7入栈
    	(3)将 5 入栈
    	(4)接下来是 × 运算符,因此弹出5 和 7,计算出35,将其入栈
    	(5)将 6 入栈
    	(7)最后是 - 运算符,计算出35 - 6,得到最后结果29
    	*/
    
    	public static int calculate(List<String> ls){
    		//创建一个栈,只需要一个栈即可
    		Stack<String> stack = new Stack<String>();
    
    		//遍历ls
    		for(String item:ls){
    			//这里使用正则表达式来取出值
    			if(item.matches("\\d+")){
    				//匹配的是多位数
    				//入栈
    				stack.push(item);
    			}else{
    				//pop出两个数并运算,再入栈
    				int num2 = Integer.parseInt(stack.pop());
    				int num1 = Integer.parseInt(stack.pop());
    				int res = 0;
    				if(item.equals("+")){
    					res = num1 + num2;
    				}else if(item.equals("-")){
    					res = num1 - num2;
    				}else if(item.equals("*")){
    					res = num1 * num2;
    				}else if(item.equals("/")){
    					res = num1 / num2;
    				}else{
    					throw new RuntimeException("运算符有误");
    				}
    				//把res入栈
    				stack.push("" + res);
    			}
    		}
    		//最后留在stack中的数据是运算结果
    		return Integer.parseInt(stack.pop());
    	}
    }
    
    
    
    
    展开全文
  • 目录结构 1.JAVA中栈的实现 数组实现 链表实现 JAVA自带Stack类 2.计算器的实现 中缀表达式(人脑熟悉) 前缀表达式(波兰表达式) 后缀表达式(逆波兰表达式) 常用 3.中缀后缀 JAVA中栈的实现 1.数组实现 ...

    目录结构

    1.JAVA中栈的实现

    • 数组实现
    • 链表实现
    • JAVA自带Stack类

    2.计算器的实现

    • 中缀表达式(人脑熟悉)
    • 前缀表达式(波兰表达式)
    • 后缀表达式(逆波兰表达式) 常用

    3.中缀转后缀


    JAVA中栈的实现

    1.数组实现

    定义类ArrayList,模拟栈
    此类具有三个属性:

    	private int maxSize;	//栈大小
    	private int[] stack;	//实现栈所用的数组   在构造方法中初始化
    	private  int top=-1;	//栈顶指针,初始值为-1
    

    具体代码如下:

    
    import java.util.Scanner;
    
    public class ArrayStackDemo {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		ArrayStack stack = new ArrayStack(4);
    		boolean flag = true;
    		Scanner scanner = new Scanner(System.in);
    		String key="";
    		while(flag){
    			System.out.println("show: 表示显示栈");
    			System.out.println("exit: 退出程序");
    			System.out.println("push: 表示添加数据到栈(入栈)");
    			System.out.println("pop: 表示从栈取出数据(出栈)");
    			System.out.println("请输入你的选择");
    			
    			key =scanner.next();
    			switch (key) {
    			case "show":
    				stack.list();
    				break;
    			case "push":
    				System.out.println("请输入一个数");
    				int value = scanner.nextInt();
    				stack.push(value);
    				break;
    			case "pop":
    				int i =stack.pop();
    				System.out.println("出栈的数为"+i);
    				break;
    			case "exit":
    				scanner.close();
    				flag=false;
    				System.out.println("退出系统");
    			default:
    				break;
    			}
    			
    		}
    		
    	}
    
    }
    /**
     *实现栈的类
     */
    class ArrayStack{
    	private int maxSize;
    	private int[] stack;
    	private  int top=-1;
    	
    	ArrayStack(int maxSize){
    		this.maxSize=maxSize;
    		stack = new int[maxSize];
    	}
    	
    	/**
    	 * 判断是否为空
    	 * @return
    	 */
    	public boolean isEmpty(){
    		return top==-1;
    	}
    
    	/**
    	 * 判断是否已满
    	 * @return
    	 */
    	public boolean isFull(){
    		return top==maxSize;
    	}
    	
    	/**
    	 * 入栈
    	 * @param i
    	 */
    	public void push(int i){
    	if(isFull()){
    		System.out.println("栈已满,添加失败");
    		return;
    	}
    	top++;
    	stack[top]=i;
    	}	
    	
    	/**
    	 * 出栈
    	 * @return
    	 */
    	public int pop() throws RuntimeException{
    		if(isEmpty()){
    			throw new RuntimeException("栈空,不能再出栈");
    		}
    		int value = stack[top];
    		top--;
    		return value;
    	}
    	
    	/**
    	 * 返回栈顶元素   不出栈
    	 * @return
    	 */
    	public int getTop(){
    		return stack[top];
    	}
    	/**
    	 * 显示数据
    	 */
    	public void list(){
    		if(isEmpty()){
    			System.out.println("栈空,没有数据");
    		}
    		for(int i=top;i>=0;i--){
    			System.out.printf("stack[%d]=%d\n",i,stack[i]);
    		}
    	}
    }
    

    2.链表实现

    定义类Node,模拟栈中的数据结点
    此类只有两个属性:

    	private int data;
    	private Node next;	//指向下一个结点的指针
    

    定义类ArrayStack2,模拟栈的实现
    此类中有一个属性,是整个栈的头结点

    	//初始化头结点
    	private Node head=new Node(0, null);
    

    具体代码如下:

    import java.util.Scanner;
    
    public class ArrayStackDemoLinked {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		ArrayStack2 stack = new ArrayStack2();
    		boolean flag = true;
    		Scanner scanner = new Scanner(System.in);
    		String key="";
    		while(flag){
    			System.out.println("show: 表示显示栈");
    			System.out.println("exit: 退出程序");
    			System.out.println("push: 表示添加数据到栈(入栈)");
    			System.out.println("pop: 表示从栈取出数据(出栈)");
    			System.out.println("请输入你的选择");
    			
    			key =scanner.next();
    			switch (key) {
    			case "show":
    				stack.list();
    				break;
    			case "push":
    				System.out.println("请输入一个数");
    				int value = scanner.nextInt();
    				stack.push(value);
    				break;
    			case "pop":
    				int i =stack.pop();
    				System.out.println("出栈的数为"+i);
    				break;
    			case "exit":
    				scanner.close();
    				flag=false;
    				System.out.println("退出系统");
    			default:
    				break;
    			}
    	 
    	}
    	}
    
    	
    }
    /**
     * 结点类
     * @author 10405
     *
     */
    class Node{
    	private int data;
    	private Node next;
    	
     	Node(int data,Node	 node){
    		this.data=data;
    		this.next=node;
    	}
    
    	public int getData() {
    		return data;
    	}
    
    	public void setData(int data) {
    		this.data = data;
    	}
    
    	public Node getNext() {
    		return next;
    	}
    
    	public void setNext(Node next) {
    		this.next = next;
    	} 
    	
    }
    
    /**
     * 栈类
     * @author 10405
     *
     */
    class ArrayStack2{
    	//初始化头结点
    	private Node head=new Node(0, null);
    	
    	/**
    	 * 判断栈是否为空
    	 * @return
    	 */
    	public boolean isEmpty(){
    		return head.getNext()==null;
    	}
    
    	/**
    	 * 入栈  使用头插法
    	 * @param value
    	 */
    	public void push(int value){
    		Node temp = new Node(value, null);
    		temp.setNext(head.getNext());
    		head.setNext(temp);
    	}
    	
    	public int pop(){
    		if(isEmpty()){
    			throw new RuntimeException("栈为空,不能出栈");
    		}
    		Node temp =head.getNext();
    		head.setNext(temp.getNext());
    		return temp.getData();
    	}
    	
    	public void list(){
    		if(isEmpty()){
    			System.out.println("链表为空");
    		}
    		Node temp=head.getNext();
    		while(temp!=null){
    			System.out.printf("%d\n",temp.getData());
    			temp=temp.getNext();
    		}
    	}
    
    }
    
    

    3.JAVA自带的Stack类

    继承自Vector
    具有如下方法:
    在这里插入图片描述


    计算器的实现

    1.使用中缀表达式

    中缀表达式是我们常见的书写格式,如:“30+2*50-10=?”。虽然这种方式人为理解很容易,但对计算机很不友好。

    思路分析:
    1.从  左向右  扫描中缀表达式,通过一个index索引来遍历
    2.new 两个栈   s1->数栈  用来存放数字   s2->符号栈 用来存放运算符
    3.若当前扫描到的字符是数字,则直接入数栈
    4.若当前扫描到的字符是符号,则分情况讨论:
    	1)若当前符号栈为空,则直接入栈
    	2)否则进行优先级比较:
    		① 若当前操作符优先级<=s1栈顶元素的优先级,则从s1  pop一个操作符  s2 pop两个操作数出来,参与运算,并将结果压入数栈。  再将当前操作符压入符号栈s1.
    		
    		>注:若是减法或除法运算,应该是  次栈顶-栈顶 
    		
    		②否则(当前符号优先级大于符号栈栈顶优先级),则直接入符号栈s1
    5.若当前表达式扫描完毕,就顺序从数栈和符号栈pop出相应的数和符号,并运行,结果压入数栈s2
    6.到最后,符号栈为空,数栈只有一个数字,就是运算最终结果
    

    2.前缀表达式(波兰表达式)

    前缀表达式的操作符都位于操作数之前
    例:“(3+4)*5-6”对应的前缀表达式为: “- * + 3 4 5 6”
    对于中缀表达式如何转化为前缀表达式,我们这里不进行详述

    给定一个前缀表达式,具体的求值过程如下:
    1.从  右向左  扫描前缀表达式
    2.只new 一个新的Stack   用来存放操作数,操作符不需要入栈
    2.遇到数字,直接入栈
    3.遇到操作符,则出栈两个操作数进行运算,结果入数栈
    
    	>注:若是减法或除法运算,应该是   栈顶-次栈顶 
    
    4.重复上述过程,直至扫描完毕
    5.最后栈中的唯一元素即是运算结果
    

    3.后缀表达式(逆波兰表达式) 最常用

    给定一个后缀表达式,具体求值过程如下:
    1.从  左向右  扫描后缀表达式
    2.只new 一个新的Stack   用来存放操作数,操作符不需要入栈
    2.遇到数字,直接入栈
    3.遇到操作符,则出栈两个操作数进行运算,结果入数栈
    
    	>注:若是减法或除法运算,应该是  次栈顶-栈顶 
    
    4.重复上述过程,直至扫描完毕
    5.最后栈中的唯一元素即是运算结果
    

    中缀转后缀表达式算法

    给定一个中缀表达式:
    1.从 左向右 扫描扫描中缀表达式
    2.初始化两个栈 s1、s2     s1是运算符栈   s2是存储中间及最后结果的栈
    3.如果遇到数字,直接压入s2
    4.否则如果是括号
    	1)左括号直接入栈s1
    	2)右括号的话,依次弹出s1栈顶操作符,并压入s2中,直至遇到“(”为止,并丢弃这对括号
    5.否则(遇到了操作符),比较其与s1栈顶元素优先级:
    	1)若s1为空,或栈顶为左括号,则直接入栈s1
    	2)否则,若优先级比s1栈顶高,也直接压入栈s1
    	3)否则,将s1栈顶元素弹出压入s2,再重复5.1,与s1中新的栈顶元素比较
    6.重复3-5步骤,直到扫描完毕
    7.将s1剩余元素依次弹出,并压入s2
    8.将s2依次出栈并输出,结果的  逆序  即为该中缀对应的后缀表达式
    

    注:我们观察到 s2中只有入栈没有出栈,且最后出栈后需要倒序排序。所以,在代码的具体实现时,我们可以用ArrayList来代替Stack s2.输出的ArrayList即为正确结果,不用再逆序排序。
    具体代码如下:

    package com.atguigu.stack;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    public class PolandNotation {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    	
    		/*//先直接给出逆波兰表达式		(30+4)*5-6
    		String	suffixExpression="30 4 + 5 * 6 - ";
    		//思路:1.先将表达式拆分开  存入List集合中
    		//	  2.将ArrayList传递给一个方法,在方法中遍历该集合,配合栈  完成计算
    		List<String> stringList = PolandNotation.getStringList(suffixExpression);
    		System.out.println(stringList);
    		
    		int res=PolandNotation.calculator(stringList);
    		System.out.println(res);
    		*/
    		
    		String expression = "1+((20+30)*4)-5";//注意表达式 
    		List<String> infixExpressionList = toInfixExpressionList(expression);
    		System.out.println("中缀表达式对应的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
    		List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
    		System.out.println("后缀表达式对应的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–] 
    		
    		System.out.printf("expression=%d", calculator(suffixExpreesionList)); // ?
    	}
    	
    	
    	/**
    	 * 将中缀表达式转换成一个List集合
    	 * @param s
    	 * @return
    	 */
    	public static List<String> toInfixExpressionList(String s) {
    		List<String> ls = new ArrayList<String>();
    		int i = 0; //这时是一个指针,用于遍历 中缀表达式字符串
    		String str; // 对多位数的拼接
    		char c; // 每遍历到一个字符,就放入到c
    		do {
    			//如果c是一个非数字,我需要加入到ls
    			if((c=s.charAt(i)) < 48 ||  (c=s.charAt(i)) > 57) {
    				ls.add("" + c);
    				i++; //i需要后移
    			} else { //如果是一个数,需要考虑多位数
    				str = ""; //先将str 置成"" '0'[48]->'9'[57]
    				while(i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) {
    					str += c;//拼接
    					i++;
    				}
    				ls.add(str);
    			}
    		}while(i < s.length());
    		return ls;//返回
    	}
    	
    	/**
    	 * 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]  =》 ArrayList [1,2,3,+,4,*,+,5,–]
    	 * 方法:将得到的中缀表达式对应的List => 后缀表达式对应的List
    	 * @param ls
    	 * @return
    	 */
    	public static List<String> parseSuffixExpreesionList(List<String> ls) {
    		//定义两个栈  s1、s2    s1存放运算符 ,  s2存放中间及结果
    		Stack<String> s1 = new Stack<>();
    		
    		List<String> s2 =new ArrayList<>();//因为s2只进栈不出栈,且最后结果需要倒序排列   所以这里直接用List  直接输出就是结果
    		
    		//遍历list
    		for(String s :ls){
    			//若是数字   直接入栈/List
    			if(s.matches("\\d+")) {
    				s2.add(s);
    			}
    			//如果是“(”
    			else if("(".equals(s)){
    					s1.push(s);
    				}
    			//如果是“)”
    			else if(")".equals(s)){
    				//从s1依次出栈   并压入s2   直到“(”出栈   并丢弃这对括号
    				String temp="";
    				while(!s1.peek().equals("(")){
    					temp=s1.pop();
    					s2.add(temp);
    				}
    				s1.pop();
    			}
    			
    			//如果是操作符  分情况:
    			else{
    				
    		/*	 	//如果栈为空或者栈顶为“(”,直接入栈
    				if(s1.isEmpty()||"(".equals(s1.peek())){
    					s1.push(s);
    				}
    				//如果优先级大于栈顶  直接入栈
    				else if(PolandNotation.getValue(s)>PolandNotation.getValue(s1.peek())){
    					 s1.push(s);
    				}
    				//如果优先级小于等于栈顶   则循环  让s1栈顶出栈  并压入s2   直到栈空或者s优先级大于栈顶元素
    				else {
    					while(!s1.isEmpty()&&PolandNotation.getValue(s1.peek())>=PolandNotation.getValue(s)){
    						s2.add(s1.pop());
    					}
    					s1.push(s);
    				} */
    				
    				/**
    				 * 经过观察  发现  上面这种写法太麻烦   因为不管怎么样  都有push这一步  只是最后一种情况多了一步   
    				 * 下面简写:
    				 */
    				 while(!s1.isEmpty()&&PolandNotation.getValue(s1.peek())>=PolandNotation.getValue(s)){
    					s2.add(s1.pop());
    				}
    				s1.push(s); 
    				
    				
    			}
    			
    		}
    		
    		//将s1中剩余的运算符依次弹出并加入s2
    		while(s1.size() != 0) {
    			s2.add(s1.pop());
    		}
    
    		return s2; //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
    	}
    	
    	/**
    	 * 返回运算符的优先级
    	 * @param s
    	 * @return
    	 */
    	public static int getValue(String s){
    		int res=0;
    		switch (s) {
    		case "+":
    			res=1;
    			break;
    		case "-":
    			res=1;
    			break;
    		case "*":
    			res=2;
    			break;
    		case "/":
    			res=2;
    			break;
    
    		default:
    			System.out.println("运算符错误,不能返回优先级"+s);
    			break;
    		}
    		return res;
    	}
    	
    	
    	/**
    	 * 将后缀表达式拆分开   成为一个List集合
    	 * @param suffixExpression
    	 * @return
    	 */
    	public static List<String> getStringList(String suffixExpression){
    		//将suffixExp分割
    		String[] strings = suffixExpression.split(" ");
    		List<String> stringList =new ArrayList<>();
    		for(String s :strings){
    			stringList.add(s);
    		}
    		return stringList;
    	}
    	
    	
    	/**
    	 * 完成对逆波兰表达式的计算
    	 * 1.从左到右扫描
    	 * 2.遇到数字,直接入栈       		注:我们只需要一个栈    因为操作符不用入栈
    	 * 3.遇到运算符    出栈两个数                注:次栈顶 - 栈顶
    	 * @param list
    	 * @return
    	 */
    	
    	public static int calculator(List<String> list){
    		Stack<String> stack=new Stack<>();
    		
    		for(String s:list){
    			if(s.matches("\\d+")){  //匹配多位数字
    				//数字直接入栈
    				stack.push(s);
    			}else{
    				//如果是操作符
    				int num1 =Integer.parseInt(stack.pop());
    				int num2 =Integer.parseInt(stack.pop());
    				int res=0;
    				switch (s) {
    				case "+":
    					res=num1+num2;
    					break;
    				case "-":
    					res=num2-num1;
    					break;
    				case "*":
    					res=num1*num2;
    					break;
    				case "/":
    					res=num2/num1;
    					break;
    				default:
    					System.out.println("操作符有误");
    					break;
    				}	
    				stack.push(res+"");
    			}
    			
    		}
    		
    		return Integer.parseInt(stack.pop());		
    	}
    	
    }
    
    
    展开全文
  • 如何将中缀表达式转换成后缀表达式 按运算符的优先级对所有的运算符和它的运算数加括号。 把运算符移到对应的括号后。 去掉括号。 前缀表达式其实将运算符提到括号的前面,其他都一样。 ...

    如何将中缀表达式转换成后缀表达式

    1. 按运算符的优先级对所有的运算符和它的运算数加括号。
    2. 把运算符移到对应的括号后。
    3. 去掉括号。

    前缀表达式其实将运算符提到括号的前面,其他都一样。

    展开全文
  • 2、中缀表达式的求值是我们人最熟悉的,但是对计算机来说却不好操作(前面我们讲的案例就能看的这个问题),因此,在计算结果时,往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.) 中缀表达式的计算机求...
  • 最近笔试的过程中老是有中缀转换为前缀,或是中缀转换为后缀的问题,数据结构学了这么久真的是记不清了,今天重新复习了一下,借此机会总结一下:    中缀:我们正常理解的表达式的书写方式;  前缀:操作符全部...
  • 前缀中缀后缀表达式及其互相转换

    万次阅读 2015-05-24 19:59:02
    计算机中前缀中缀后缀表达式是数据结构栈的重要应用,他们都是对表达式的记法,只是相对位置不一样,顾名思义,前缀表达式指的是符号都在操作数之前,中缀表达式指的是运算符都在操作数之后,而后缀表达式是之后。...
  • 前缀表达式(Prefix Notation)是指将运算符写在前面操作数写在后面的不包含括号的表达式,而且为了纪念其发明者波兰数学家JanLukasiewicz,所以前缀表达式也叫做“波兰表达式” 后缀表达式(Postfix Notation)与之相反...
  • } } 三种表达式(前缀 中缀 后缀) 前缀表达式(波兰表达式) 前缀表达式又称波兰式,前缀表达式的运算符位于操作数之前 举例说明: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 前缀表达式的计算机求值 从右至左...
  • 前缀中缀后缀表达式

    2013-04-18 18:08:35
    中缀表达式转换为前缀表达式的3种方法,链接如下: ...所以抽几天时间复习一下数据结构。看到堆栈部分,有一个运用堆栈的列子,表达式的中缀前缀后缀的转换,刚开始找工作面试和笔试都遇到了这样的问题
  • 虽然人的大脑很容易理解与分析中缀表达式,但对计算机来说中缀表达式却是很复杂的,因此计算表达式的值时,通常需要先将中缀表达式转换为前缀后缀表达式,然后再进行求值。对计算机来说,计算前缀后缀表达式的值...
  • 前缀表达式的计算机求值:从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(栈顶元素 op 次顶元素),并将结果入栈;重复上述过程直到表达式最左端,...
  • 中缀表达式 中缀表达式是一个通用的算术或逻辑公式表示方法, 操作符是以中缀形式处于操作数的中间(例:3 + 4),中缀表达式是人们常用的算术表示方法。中缀记法中括号是必需的。计算过程中必须用括号将操作符和...
  • 2.1 中缀表达式 转 前缀表达式 2.2 中缀表达式 转 后缀表达式 2.3 后缀表达式 转 中缀表达式 2.4 后缀表达式 转 前缀表达式 3. 表达式的转换 - 用栈实现 3.1 中缀后缀 代码 3.1 中缀前缀 3.2 后缀前缀...
  • 数据结构-前缀中缀后缀表达式

    千次阅读 2016-07-27 11:29:12
    它们都是对表达式的记法,因此也被称为前缀记法、中缀记法和后缀记法。它们之间的区别在于运算符相对与操作数的位置不同:前缀表达式的运算符位于与其相关的操作数之前;中缀后缀同理。 举例: (3 + 4) × 5 - 6 ...
  • 一、中缀后缀 1、从左往右扫描中缀表达式,如果是数字,写入结果表达式,如果是操作数,需要进一步判断 2、(1)如果是左括号’(’,直接入栈 (2)如果是运算符,(‘+’、...下面是天勤数据结构视频中的一道例题:
  • 前缀表达式:前缀表达式是一种没有括号的算数表达式,它将运算符写在前面,操作数写在后面 中缀表达式:操作符处于操作数的中间。中缀表达式是人们常用的算术表示方法 后缀表达式:运算符位于操作数之后 举例: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 485
精华内容 194
关键字:

数据结构前缀中缀后缀

数据结构 订阅