嘉兴专业做网站,wordpress 多个边栏,wordpress固定连接重,网站建设服务兴田德润一元一次方程–逆波兰栈
【题目摘要】 题目描述 SLON是一个调皮的学生#xff0c;为了让他静下心来#xff0c;老师给他出了一道数学题#xff1a;
给定表达式A#xff0c;A中含有变量x和,-,*,(,)这些符号#xff0c;括号成对出现#xff0c;一个算术运算符均对应两个操…一元一次方程–逆波兰栈
【题目摘要】 题目描述 SLON是一个调皮的学生为了让他静下心来老师给他出了一道数学题
给定表达式AA中含有变量x和,-,*,(,)这些符号括号成对出现一个算术运算符均对应两个操作数不能出现(-5)或者(4±5)等乘号不能省略并且表达式A中x只能是一阶即一阶表达式
合理表达式A5 x∗(3 2) or x 3∗x 4∗(5 3∗(2 x−2∗x)).
不合理表达式A5∗(3 x∗(3 x)) or x∗(x x∗(1 x)).
求A%MP时最小的x
输入格式 The first line of input contains the expression A (1 ≤|A|≤ 100000).
The second line of input contains two integers P (0 ≤ P ≤ M −1) i M (1 ≤ M ≤ 1000000).
The arithmetic expression A will only consists of characters , -, *, (, ), x and digits from 0 to 9.
The brackets will always be paired, the operators , - and * will always be applied to exactly two values (there will not be an expression (-5) or (4±5)) and all multiplications will be explicit (there will not be an expression 4(5) or 2(x)).
输出格式 输出最小的非负x
样例 样例输入1 53x 9 10 样例输出1 1 样例输入2 203x 0 5 样例输出2 2 样例输入3 3*(x(x4)*5) 1 7 样例输出3 1
【思路正解】
部分小细节处理会在代码中体现并解释 首先看见这个带括号的中缀式 二话不说掏出 葵花宝典 前缀式or后缀式模板 它们的小跟班–小栈栈也会出现 woc前缀式or后缀式是神马玩意儿 只需要打开手机电脑搜索 你最喜欢的小姐姐小哥哥pick 她他吧 前缀式和后缀式有许多好文章可以帮助你理解
【概括一下】从左到右遍历中缀表达式的每个数字和符号若是数字就不管直接入栈若是符号则判断其与栈顶符号的优先级是右括号或者优先级不高于栈顶符号乘除优先加减则栈顶元素依次出栈 并将当前符号进栈
如此一来只要你有模板在手天下你有 咳咳咳–回归正题 怎么想到后缀式的 思考一下最后计算完的式子f(x) kx b 这个时候你就可以令x为零 算出f(0)也就是b的值 还可以算出令x为一f(1)也就是kb的值结合上面已经算出的b的值就可以暴力求出了k的值那么x就自然而然出来了 如何计算f(0)和 f(1)的表达式当然得用栈把中缀表达式改为后缀表达式 所以总结套路见中缀一定要想后缀和前缀
码力有限瞅瞅【代码实现】
#include cstring
#include cstdio
#include stack
using namespace std;
#define LL long long
#define MAXN 100005
struct node {LL a, b; //a为x系数 b为常数 node () {}node ( LL A, LL B ) {a A;b B;}
};
stack char mark; //存运算符
stack node constant; //存常数
int p, m, len;
char s[MAXN]; bool check ( char x, char y ) {if ( x ( || y ( ) return 0;if ( x * || y ) || y || y - ) return 1;return 0;
}node count ( node x, node y, char z ) {node ans;switch ( z ) {//通过题目了解到x一定是一次项所以在算乘法的时候x,y两个当中一定有一个的系数为0//(kxb)*a这种类似的就直接加不影响结果实在理解不了举个栗子就可以啦case * : ans.a ( x.a * y.b x.b * y.a ) % m;ans.b ( x.b * y.b ) % m;break;case : ans.a ( x.a y.a ) % m;ans.b ( x.b y.b ) % m;break;case - : ans.a ( y.a - x.a m ) % m;ans.b ( y.b - x.b m ) % m;break;/**减法一定不要写成x.a-y.a因为think about it我们用的是栈先进后出我们传过来的参数看下面x在y前面那么反推它就是中缀式的减数**///减法有可能简称负数因此要加一个mod}return ans;
}int main() {scanf ( %s, s );scanf ( %d %d, p, m );len strlen ( s );s[len] );/*随便一个正确的式子最后一个肯定是数字或者x那么我们后面的代码无法让它参与到大家庭的计算当中就在最后加个右括号逼着它join*/mark.push ( ( );for ( int i 0;i len;i ) {if ( s[i] x ) {constant.push ( node ( 1, 0 ) );}else if ( s[i] 0 s[i] 9 ) {LL x s[i] - 0;while ( s[i 1] 0 s[i 1] 9 ) {i ;x ( ( x 1 ) ( x 3 ) ( s[i] - 0 ) ) % m;}constant.push( node ( 0, x ) );}else {while ( check ( mark.top(), s[i] ) ) {node x constant.top();constant.pop();node y constant.top();constant.pop();char z mark.top();mark.pop();node result count ( x, y, z );constant.push( result );}if ( s[i] ) ) mark.pop();/*如果是右括号check会一直返回1我们就会一直计算直到碰见它的另一半~~多么痴情一男的~~ 那么跳出while后就把这个左括号踢出去~它已经失宠了*/else mark.push( s[i] );}}node result constant.top();//p一定小于m所以x一定不为0不然这就是个戴了面具的方程for ( LL i 1;;i )//可以暴力美剧如果前面写得好就可以不用担心if ( ( result.a * i result.b ) % m p )return ! printf ( %lld, i );return 0;
}
