今天讲的字符串:
不多说, 直接看题
一. 表达式求值
题目大意:
输入一行一个表达式, 计算其答案 表达式包含非负整数加减乘除括号
两种做法
. 栈
. 表达式树
这里更推荐表达式树, 因为栈是先压进去, 逆序操作在进行逆序操作时即从右往左计算, 实际应该是从左往右计算, 所以会出现计算不符合顺序的问题从而出现错误
而表达式树则又称为表达式目录树, 以数据形式表示语言级代码, 它是一种抽象语法树或者说是一种数据结构摘自百度百科
可见, 每个父节点都是一种运算符, 子节点为数字运算时从底层向上层依次按父节点符号操作子节点即可
先贴栈的代码:
- /*
- 1+(2+3)*4
- 21
- */
- #include <iostream>
- #include <stack>
- using namespace std;
- const int MAXN = 10000 + 10;
- char str[MAXN];
- stack<int> nums;
- stack<char> symbol;
- void pop()
- {
- int a = nums.top();nums.pop();
- int b = nums.top();nums.pop();
- char s = symbol.top();symbol.pop();
- int ans;
- switch(s)
- {
- case +:ans=a+b;break;
- case -:ans=b-a;break;
- case *:ans=a*b;break;
- case /:ans=b/a;break;
- }
- nums.push(ans);
- }
- int main()
- {
- cin >> (str+1);
- for(int i=1;str[i]!=0;i++)
- {
- char c=str[i];
- if(0<=c&&c<=9)
- {
- nums.push(c-0);
- } else {
- if(c==))
- {
- while(symbol.top() != () pop();
- symbol.pop();
- } else if (c==+ || c==-)
- {
- while(!symbol.empty()
- &&symbol.top()!=+
- &&symbol.top()!=-
- &&symbol.top()!=() pop();
- symbol.push(c);
- } else symbol.push(c);
- }
- }
- while(!symbol.empty())pop();
- cout<<nums.top()<<endl;
- return 0;
- }
在计算上面图中的例子时, 栈会出错
下面给出表达式树的代码:
- /*
- 10+(2+3)*4
- 30
- */
- #include <iostream>
- #include <stack>
- #include <cstring>
- using namespace std;
- const int MAXN = 10000 + 10;
- char str[MAXN];
- int solve(int l, int r)
- {
- int pos=-1;
- int flag=0;
- int level=2; // 0:+- 1:*/
- for(int i=l;i<=r;i++)
- {
- if(str[i]==()flag++;
- if(str[i]==))flag--;
- if(flag == 0 && (str[i]<0||str[i]>9||str[i]==+||str[i]==-||str[i]==*||str[i]==/)&&str[i]!=))
- {
- int l=-1;
- switch(str[i])
- {
- case +:case -:l=0;break;
- case *:case /:l=1;break;
- }
- if(level >= l)
- {
- level=l;
- pos=i;
- }
- }
- }
- if(pos==-1)
- {
- if(str[l]==(&&str[r]==)) return solve(l+1,r-1);
- int x=0;
- for(int i=l;i<=r;i++)
- x=x*10+str[i]-0;
- return x;
- }
- int a = solve(l, pos-1);
- int b = solve(pos+1, r);
- int ans;
- switch(str[pos])
- {
- case +:ans=a+b;break;
- case -:ans=a-b;break;
- case *:ans=a*b;break;
- case /:ans=a/b;break; // 3*2/3
- }
- return ans;
- }
- int main()
- {
- cin >> (str+1);
- cout << solve(1, strlen(str+1)) << endl;
- return 0;
- }
二. 字符串统计
题目大意: 给定 N 个字符串, 判断不同的字符串有多少个
做法: hash
所谓 hash 就是把每个字符串设成一个值, 每个字符串的值要不同, 所以操作的时候只要弄的奇奇怪怪就好啦 (个人理解, 不喜勿喷)
这样比较字符串就成了比较数值的问题
哈希碰撞: 所谓哈希碰撞是指在哈希时难免会遇到有重复的数值, 解决方案可以为双哈希
例如: 在哈希时会模一个很大的质数, 假设这个质数为 mod, 当遇到某个数 m 时 (m<mod)m % mod = m
但是当遇到另一个数 n 时, n 恰巧为 m + mod 那么 n % mod = m 两串字符对应值都为 m, 产生了碰撞
在洛谷有道模板题, 链接: https://www.luogu.org/problemnew/show/P3370
hash 代码如下:
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- long n;
- char s[10001];
- long long ms[10101]={0};
- long long ans=1;
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- cin>>s;
- int len=strlen(s);
- for(int j=0;j<len;j++)
- ms[i]=(ms[i]*131+(long long)s[j])%233333333333+233317;
- }
- sort(ms+1,ms+n+1);
- for(int i=1;i<n;i++)
- {
- if(ms[i]!=ms[i+1])
- ans++;
- }
- printf("%d",ans);
- }
来源: http://www.bubuko.com/infodetail-2507220.html