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

# 856. Score of Parentheses

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

## 題目:

## 解題想法:
* 此題為給一字串，字串只會出現"("、")"兩字元，且一定為有效括號
* 一組有效括號為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為左括號

            tmp=0
            while last!='(': 
                tmp+=last
                last=stack.pop()
            stack.append(2*tmp)

* 累加stack即為解

## 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++:

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;
    }
};