使用Stack求解字符串表达式

Question

我正试图像下面的示例测试用例一样扩展给定的字符串。

样本输入和输出

Input : a(b(c){2}){2}d
Output:  abccbccd
Input:  ((x){3}(y){2}z){2}
Output: xxxyyzxxxyyz

下面的代码适用于上面的测试用例，但我想知道是否有比这更好的方法，因为我对这个解决方案没有信心。欢迎使用ArrayList作为堆栈的任何解决方案。

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
String temp = "";
String alpha = "";
ArrayList<String> stack = new ArrayList<>();

for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);

if (ch == '(') {
stack.add(""+ch);
} else if (ch >= 'a' && ch <= 'z') {
alpha += ch;
if (!stack.isEmpty() && !stack.get(stack.size()-1).equals("(")) {
alpha = stack.remove(stack.size()-1) + alpha;
}
stack.add(alpha);
alpha = "";
} else if (ch == ')') {
temp = stack.remove(stack.size()-1);

for(; !stack.get(stack.size()-1).equals("(");) {
temp = stack.remove(stack.size()-1) + temp;
}
stack.remove(stack.size()-1);
stack.add(temp);
} else if (ch == '{') {
i++;
temp = stack.remove(stack.size()-1);
String t = temp;
if(s.charAt(i)=='0') {
temp = "";
}
for(int j = 1; j < s.charAt(i)-48; j++) {
temp += t;
}
i++;
if (s.charAt(i) == '}') {
stack.add(temp);
}
}
}
System.out.print(stack);
}

Answer 1

我不认为使用ArrayList是最适合您的代码的方法。从Java 1.5开始，您可以使用StringBuilder在字符串缓冲区内连接字符。您的代码将更快，使用更少的内存。

使用String实例：

str += other;

相当于：

str = str + other;

，因此操作为O(str.length((+other.length(.

使用StringBuilder实例：

str.append(other)

操作仅为O(other.length(((.

左侧串联也是如此。说明：

str = other + str;

将替换为：

str.insert(0, other);

您的代码看起来是这样的(我添加了一个switch-case，它比多个if语句稍微快一点(：

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
StringBuilder temp = new StringBuilder();
StringBuilder alpha = new StringBuilder();
ArrayList<String> stack = new ArrayList<>();

for (int i = 0, len = s.length(); i < len; i++) {
char ch = s.charAt(i);
switch(ch) {
case '(':
stack.add("" + ch);
break;
case ')':
temp = new StringBuilder(stack.remove(stack.size() - 1));
for(; !stack.get(stack.size()-1).equals("(");) {
String last = stack.remove(stack.size()-1);
temp.insert(0, last);
}
stack.remove(stack.size() - 1);
stack.add(temp.toString());
break;
case '{':
i++;
temp = new StringBuilder(stack.remove(stack.size() - 1));
String t = temp.toString();
if (s.charAt(i) == '0')
temp.setLength(0);
for(int j = 1; j < s.charAt(i) - 48; j++)
temp.append(t);
i++;
if (s.charAt(i) == '}')
stack.add(temp.toString());
break;
default:
if (ch >= 'a' && ch <= 'z') {
alpha.append(ch);
if (!stack.isEmpty() && !stack.get(stack.size()-1).equals("(")) {
String last = stack.remove(stack.size()-1);
alpha.insert(0, last);
}
stack.add(alpha.toString());
alpha.setLength(0); // Clears the string buffer
}
break;
}
}
System.out.print(String.join("", stack));
}