---
# System prepended metadata

title: 856. Score of Parentheses
tags: [string, Leetcode, stack, medium, python, c++]

---

###### tags: `Leetcode` `medium` `stack` `string` `python` `c++`

# 856. Score of Parentheses

## [題目連結:] https://leetcode.com/problems/score-of-parentheses/

## 題目:
![](https://i.imgur.com/iNOKtQb.png)
![](https://i.imgur.com/tggxwnT.png)


## 解題想法:
* 此題為給一字串，字串只會出現"("、")"兩字元，且一定為有效括號
    * 一組有效括號為1分
    * 若括號內有其他分數，則分數乘2
    * 求總分
* 括號題目，往stack思考
    * 初始定義:
        * stack=[]: **只存左括號與數字**
            * python可以混存
            * c++則可以將左括號視為0存入
    * for char in s:遍歷s字串
        * case1:若當前char=='(': 等於左括
            * 存入stack
        * case2: 否則當前char為右括號，**不可存入stack**
            * **技巧: 需判斷stack中最頂的值**
                * last==stack.pop()
            * case2-1: 若last=='(' 為左括號
                * 表示可以成功構成1，將1加入於stack
            * case2-2: 否則last為數字:
                * 持續累加直到last為左括號
             ``` python=
            tmp=0
            while last!='(': 
                tmp+=last
                last=stack.pop()
            stack.append(2*tmp)
             ```
     * 累加stack即為解

## Python:
``` python=
class Solution(object):
    def scoreOfParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        stack=[] #只存'('or 數字
        for char in s:
            if char=='(':
                stack.append(char)
            else: #若當前char為')'，則不要存入stack
                last=stack.pop()
                if last=='(':
                    stack.append(1)
                else: #last為數字
                    tmp=0
                    while last!='(': 
                        tmp+=last
                        last=stack.pop()
                    stack.append(2*tmp)
        return sum(stack)
```

## C++:
``` cpp=
class Solution {
public:
    int scoreOfParentheses(string s) {
        stack<int> tmp;
        for (char val: s){
            if (val=='(')
                tmp.push(0);
            else{
                int last=tmp.top(); tmp.pop();
                if (last==0)
                    tmp.push(1);
                else{
                    int curSum=0;
                    while (last!=0){
                        curSum+=last;
                        last=tmp.top(); tmp.pop();
                    }
                    tmp.push(2*curSum);
                }
            }
        }
        //accumulate sum
        int sum=0;
        while (!tmp.empty()){
            int curVal=tmp.top(); tmp.pop();
            sum+=curVal;
        }
        return sum;
    }
};
```