文章目录

平衡符号

说明

  1. 通过栈的特性。
    模拟编译器检查程序的语法错误。
  2. （简化版）只检查 [、{、(、}、]、}、)、}，是否有前有后。
  3. 运行时间O(N)

代码

package cn.edut.test_stack;

import java.util.Arrays;
import java.util.Stack;

import org.junit.Test;

public class Demo_Stack {
	
	@Test
	public void test001() {
		String sTrue = "public boolean isLegal(String inputString) {\r\n" + 
				" Stack<Integer> sIndex = new Stack<>() ; // 存符号对应index的栈\r\n" + 
				" char[] cs = inputString.toCharArray();\r\n" + 
				" char[] prevChar = {'[','{','('};\r\n" + 
				" char[] endChar = {']','}',')'};" +
				" }" ; //true
		System.out.println(isLegal(sTrue)); //true
		
		String sFalse = "public boolean isLegal(String inputString) {" ;
		System.out.println(isLegal(sFalse)); //false
	}
	
	public boolean isLegal(String inputString) {
		Stack<Integer> sIndex = new Stack<>() ; // 存符号对应index的栈
		char[] cs = inputString.toCharArray();
		char[] prevChar = {'[','{','('};
		char[] endChar = {']','}',')'};
		 
		for(int i=0 ; i<cs.length ; i++) {
			int index = Arrays.binarySearch(prevChar, cs[i]);//找到符号
			if(index>0) {//
				sIndex.push(index);  
			}
			if(!sIndex.isEmpty()) { //栈有值,进入循环，
				int temp = sIndex.pop();
				if(endChar[temp] != cs[i] ) {
					sIndex.push(temp) ; 
				} 
			}
		}
		if(sIndex.isEmpty()) {
			return true;
		}
		return false;
	}
}

后缀表达式求值

说明

  1. 数字、符号间需要用空格隔开
  2. 运行时间O(N)

中缀转后缀写了一个完整的计算器
仅后缀表达式求值的代码：(https://blog.csdn.net/LawssssCat/article/details/102981388)

中缀转后缀（递归实现）

说明

  1. 尝试用迭代写的（网上好多都是传统算法）
  2. 时间复杂度O(N)

算法思路

  1. 定义一个<mark>全局的</mark>指针，记录遍历到的位置

  2. <mark>没有遇到“（”前</mark>，使用传统算法：
    2.1. 遍历表达式，
    2.2. 遇到数字就进结果，遇到运算符就取出栈顶，进行运算符的优先级比较，最后进栈
    （栈顶比较规则：栈顶优先级高，就进运算结果。否则就返回栈顶次位。）

  3. <mark>当遇到“（”后，进入迭代</mark>，新创建一个空的栈和List返回值。从现在的位置继续遍历表达式。直到遇到“）”。

  4. <mark>当遇到“）”，立即返回</mark>。返回值和上一个迭代的返回值合并（如果有的话）。然后，继续上一级迭代的遍历。

  5. 当全局<mark>指针指向末尾</mark>，指针初始化，返回计算的值。

代码

结合上面的后缀求值，就直接写了一个完整的Calculator。
代码链接：https://blog.csdn.net/LawssssCat/article/details/102985652