正文

leetcode：栈

IP云
IP云V管理员/5 阅读
10/04
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

1. evaluate-reverse-polish-notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are+,-,*,/. Each operand may be an integer or another expression.

Some examples:

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6用一个栈存储操作数，遇到操作数直接压入栈内，遇到操作符就把栈顶的两个操作数拿出来运算一下，然后把运算结果放入栈内。

public class Solution {
public int evalRPN(String[] tokens) {
int ret = 0;
Stack<Integer> num = new Stack<Integer>();
for (int i = 0; i < tokens.length; i++) {
if (isOperator(tokens[i])) {
int b = num.pop();
int a = num.pop();
num.push(calc(a, b, tokens[i]));
} else {
num.push(Integer.valueOf(tokens[i]));
}
}
ret = num.pop();
return ret;
} boolean isOperator(String str) {
if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/"))
return true;
return false;
} int calc(int a, int b, String operator) {
char op = operator.charAt(0);
switch (op) {
case '+': return a + b;
case '-': return a - b;
case '*': return a * b;
case '/': return a / b;
}
return 0;
}
}

2. Longest Valid Parentheses

Given a string containing just the characters ‘(‘ and ‘)‘, find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

给定一个字符串值包含字符‘(‘ and ‘)‘，找出最长有效括号子串。

对于 "(()",最长有效子串为"()",长度为2.

另一个例子是")()())"，其中的最长有效括号子串为"()()"，长度为4.

  1. stack里面装的一直是“还没配好对的括号的index”
  2. 是’(‘的时候push
  3. 是’)‘的时候，说明可能配对了；看stack top是不是左括号，不是的话，push当前右括号
  4. 是的话，pop那个配对的左括号，然后update res：i和top的（最后一个配不成对的）index相减，就是i属于的这一段的当前最长。如果一pop就整个栈空了，说明前面全配好对了，那res就是最大=i+1

public class Solution
{
public int longestValidParentheses(String s)
{
int res = 0;
Stack<Integer> stack = new Stack<Integer>();
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++)
{ //Pop()取出栈顶元素，栈顶元素被弹出Stack；
//Peek()读得栈顶元素，但栈顶元素没有被弹出Stack。
if (arr[i] == ')' && !stack.isEmpty() && arr[stack.peek()] == '(')
{
stack.pop();
if (stack.isEmpty())
res = i + 1;
else
res = Math.max(res, i - stack.peek());
}
else
{
stack.push(i);
}
}
return res;
}
}

3. vali parentheses

Given a string containing just the characters'(',')','{','}','['and']', determine if the input string is valid.

The brackets must close in the correct order,"()"and"()[]{}"are all valid but"(]"and"([)]"are not.

一个个检查给的characters，如果是左括号都入栈；如果是右括号，检查栈如果为空，证明不能匹配，如果栈不空，弹出top，与当前扫描的括号检查是否匹配。

全部字符都检查完了以后，判断栈是否为空，空则正确都匹配，不空则证明有没匹配的。

注意：

检查字符是用==，检查String是用.isEqual()，因为String是引用类型，值相等但是地址可能不等。

public boolean isValid(String s) {
if(s.length()==0||s.length()==1)
return false; Stack<Character> x = new Stack<Character>();
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='['){
x.push(s.charAt(i));
}else{
if(x.size()==0)
return false;
char top = x.pop();
if(s.charAt(i)==')')
if(top!='(')
return false;
else if(s.charAt(i)=='}')
if(top!='{')
return false;
else if(s.charAt(i)==']')
if(top!='[')
return false;
}
}
return x.size()==0;
}