基础算法题——单词记忆方法（栈）

àì夳堔傛蜴生んèń 2022-12-11 12:19 139阅读 0赞

### 单词记忆方法 ###

[题目链接][Link 1]  
![题目1][1]  
![题目2][2]  
![备注][20200930171211942.png_pic_center]

--------------------

对于这些左右括号的问题，很直接能够想到用栈来解决。

##### 解题思路 #####

①、s\[i\] == ‘(’：  
移动 tp 栈顶指针，准备将新元素压入栈顶。

if(s[i]=='('){ 
    	stk[++tp]=0;
    }

②、s\[i\] >= ‘A’ && s\[i\] <= ‘Z’：  
压栈。在字母后面可能跟着数字，所以从 i + 1 开始求出其后的数字，最终结果为数字与字符对应的数值相乘。

else if(s[i]>='A'&&s[i]<='Z'){ 
    	ll now=0, num=s[i]-'A'+1;
    	while(s[i+1]>='0'&&s[i+1]<='9')
    		now = now*10+s[i+1]-'0', i++;
    	if(now==0) now=1;
    	
    	stk[tp] += now*num;
    }

③、s\[i\]==‘)’：  
当前栈顶的元素可以与第 tp - 1 个元素合并。’)’ 后可能跟着数字，所以从 i + 1 开始求出其后的数字，与字符对应的数值相乘求出 stk\[tp\] 有括号右边是否有数值，然后就可以可以与第 tp - 1 个元素合并。

else if(s[i]==')'){ 
    	ll now=0;
    	while(s[i+1]>='0'&&s[i+1]<='9')
    		now = now*10+s[i+1]-'0', i++;
    	if(now==0) now=1;
    	
    	stk[tp-1] += now * stk[tp];
    	tp--;
    }

--------------------

AC代码

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    string s;
    ll stk[100010];
    
    int main(){ 
    	cin>>s;
    	int tp=0;
    	stk[tp]=0;
    	for(int i=0; i<s.size(); i++){ 
    		if(s[i]=='('){ 
    			stk[++tp]=0;
    		}
    		else if(s[i]>='A'&&s[i]<='Z'){ 
    			ll now=0, num=s[i]-'A'+1;
    			while(s[i+1]>='0'&&s[i+1]<='9')
    				now = now*10+s[i+1]-'0', i++;
    			if(now==0) now=1;
    			
    			stk[tp] += now*num;
    		}
    		else if(s[i]==')'){ 
    			ll now=0;
    			while(s[i+1]>='0'&&s[i+1]<='9')
    				now = now*10+s[i+1]-'0', i++;
    			if(now==0) now=1;
    			
    			stk[tp-1] += now * stk[tp];
    			tp--;
    		}
    	}
    	cout<<stk[0];
    	return 0;
    }

[参考博客][Link 2]

[Link 1]: https://ac.nowcoder.com/acm/contest/7412/C
[1]: /images/20221123/54e1b99890bf4e648f87922215466d6f.png
[2]: /images/20221123/6f7f5f64d3e2462f9c6a0e90339002ee.png
[20200930171211942.png_pic_center]: /images/20221123/913de20cced04b928e9530491f9e9702.png
[Link 2]: https://ac.nowcoder.com/acm/discuss/blogs?tagId=138742