本文共 1621 字，大约阅读时间需要 5 分钟。

平衡符号

说明

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
   
     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
    
      sIndex = new Stack<>() ; // 存符号对应index的栈		char[] cs = inputString.toCharArray();		char[] prevChar = {
   '[','{','('};		char[] endChar = {
   ']','}',')'};		 		for(int i=0 ; i
     
      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)

中缀转后缀写了一个完整的计算器

仅后缀表达式求值的代码：()

中缀转后缀（递归实现）

说明

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

算法思路

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

2. 没有遇到“（”前，使用传统算法：

   2.1. 遍历表达式，
   2.2. 遇到数字就进结果，遇到运算符就取出栈顶，进行运算符的优先级比较，最后进栈
   （栈顶比较规则：栈顶优先级高，就进运算结果。否则就返回栈顶次位。）

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

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

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

代码

结合上面的后缀求值，就直接写了一个完整的Calculator。

转载地址：https://lawsssscat.blog.csdn.net/article/details/102962279 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！