FZU2215 Simple Polynomial Problem(中缀表达求值)

By | 12月31日
Advertisement

比赛时没做出这题太可惜了。

赛后才反应过来这就是个中缀表达式求值,数字栈存的不是数字而是多项式。

而且,中缀表达式求值很水的,几行就可以搞定。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 struct Poly{
 6     long long a[1111];
 7     Poly operator+(const Poly &p)const{
 8         Poly np={0};
 9         for(int i=0; i<1111; ++i){
10             np.a[i]=(a[i]+p.a[i])%1000000007;
11         }
12         return np;
13     }
14     Poly operator*(const Poly &p)const{
15         Poly np={0};
16         for(int i=0; i<1111; ++i){
17             if(a[i]==0) continue;
18             for(int j=0; j<1111; ++j){
19                 if(p.a[j]==0) continue;
20                 np.a[i+j]+=a[i]*p.a[j];
21                 np.a[i+j]%=1000000007;
22             }
23         }
24         return np;
25     }
26 }pstk[1111];
27 char ostk[1111]={'#'};
28 int ptop,otop,pri[333];
29 void push(char op){
30     if(ostk[otop]=='#' && op=='#') return;
31     if(ostk[otop]=='(' && op==')'){
32         --otop;
33         return;
34     }
35     if(pri[ostk[otop]]<pri[op] || ostk[otop]=='('){
36         ostk[++otop]=op;
37         return;
38     }
39     if(ostk[otop--]=='+'){
40         Poly p=pstk[ptop]+pstk[ptop-1];
41         ptop-=2;
42         pstk[++ptop]=p;
43     }else{
44         Poly p=pstk[ptop]*pstk[ptop-1];
45         ptop-=2;
46         pstk[++ptop]=p;
47     }
48     push(op);
49 }
50 void output(Poly &p){
51     int i=1110;
52     while(i>=0 && p.a[i]==0) --i;
53     if(i==-1){
54         puts("0");
55         return;
56     }
57     for(int j=i; j>=0; --j){
58         printf("%I64d",p.a[j]);
59         if(j) putchar(' ');
60     }
61     putchar('\n');
62 }
63 int main(){
64     pri['+']=2; pri['*']=3;
65     pri['(']=4; pri[')']=1;
66     pri['#']=1;
67     int t;
68     char str[1111];
69     scanf("%d",&t);
70     while(t--){
71         scanf("%s",str);
72         ptop=0; otop=1;
73         for(int i=0;str[i];++i){
74             if(str[i]>='0' && str[i]<='9'){
75                 Poly p={0};
76                 p.a[0]=str[i]-'0';
77                 pstk[++ptop]=p;
78             }else if(str[i]=='x'){
79                 Poly p={0};
80                 p.a[1]=1;
81                 pstk[++ptop]=p;
82             }else{
83                 push(str[i]);
84             }
85         }
86         push('#');
87         output(pstk[ptop]);
88     }
89     return 0;
90 }

Similar Posts:

  • 栈的应用实例---中缀表达式求值

    1.中缀表达式求值实现类 package edu.tcu.soft; import java.util.Stack; /** * 功能:中缀表达式直接求值 */ public class NifixExpre { // 定义操作数栈和操作符栈 private Stack<Integer> operateNum = new Stack<Integer>(); private Stack<Character> operateChara = new Stack<Char

  • 中缀表达式求值整数

    #include<stdio.h> #include<stdlib.h> #define MAX 50 typedef struct { chardata[MAX]; inttop; }stack; typedef struct { floatdata[MAX]; inttop; }fstack;stack* create() { stack*s; s=malloc(sizeof(stack)); s->top=-1; returns; } fstack* fcreate()

  • 【数据结构】栈的应用 I :表达式求值

    1. 介绍 表达式分为前缀.中缀.后缀.前缀表达式,也称为波兰表达式,其特点是将操作符置于操作数的前面.后缀表达式,也成为逆波兰表达式,所有操作符置于操作数的后面.波兰表达式.逆波兰表达式均是由波兰数学家Jan Łukasiewicz所提出的.中缀表达式将操作符放在操作数中间.前缀表达式和后缀表达式相对于中缀表达式最大的不同是,去掉了表示运算优先级的括号. 1.1 前缀表达式求值 求值过程中会用到栈,用以存储操作数和中间运算结果. 从右至左扫描前缀表达式,进行如下操作: (1)若遇到操作数,则操

  • 表达式求值算法

    编写代码对算术表达式求值的经典方法由 Donald Knuth 描述于 1962 年(请参阅 参考资料).Knuth 将此概括为三个步骤: 对中缀表达式进行语法分析 中缀表达式到后缀表达式的转换 对后缀表达式求值 注意到我们谈到的这个经典算法有些简化:算术表达式只包含操作数.二元操作符和一种括号.此外,对于每个操作数和操作符,只用单个字符表示,使语法分析直观. 表达式表示法 算术表达式中最常见的表示法形式有 中缀.前缀和 后缀表示法.中缀表示法是书写表达式的常见方式,而前缀和后缀表示法主要用于计

  • 中缀表达式转换成后缀表达式以及逆波兰表示法求值

    中缀表达式转换成后缀表达式 算法: 中缀表达式转后缀表达式的方法: 1.遇到操作数:直接输出(添加到后缀表达式中) 2.栈为空时,遇到运算符,直接入栈 3.遇到左括号:将其入栈 4.遇到右括号:执行出栈操作,并将出栈的元素输出,直到弹出栈的是左括号,左括号不输出. 5.遇到其他运算符:加减乘除:弹出所有优先级大于或者等于该运算符的栈顶元素,然后将该运算符入栈 6.最终将栈中的元素依次出栈,输出. 例子: a+b*c+(d*e+f)*g ----> abc*+de*f+g*+ 遇到a:直接输出:

  • nyoj-409 郁闷的C小加(三) (表达式求值,中缀式转前缀式,中缀式转后缀式)

    郁闷的C小加(三) 时间限制:1000 ms | 内存限制:65535 KB 难度:4 描述 聪明的你帮助C小加解决了中缀表达式到后缀表达式的转换(详情请参考"郁闷的C小加(一)"),C小加很高兴.但C小加是个爱思考的人,他又想通过这种方法计算一个表达式的值.即先把表达式转换为前缀和后缀表达式,再求值.这时又要考虑操作数是小数和多位数的情况. 输入 第一行输入一个整数T,共有T组测试数据(T<10). 每组测试数据只有一行,是一个长度不超过1000的字符串,表示这个运算式,每个运

  • 中缀表达式转换为前缀及后缀表达式并求值(java实现)

    转载自:http://www.java3z.com/cwbwebhome/article/article8/83542.html?id=4612 它们都是对表达式的记法,因此也被称为前缀记法.中缀记法和后缀记法.它们之间的区别在于运算符相对与操作数的位置不同:前缀表达式的运算符位于与其相关的操作数之前:中缀和后缀同理. 举例: (3 + 4) × 5 - 6 就是中缀表达式 - × + 3 4 5 6 前缀表达式 3 4 + 5 × 6 - 后缀表达式 中缀表达式(中缀记法) 中缀表达式是一种通

  • 表达式求值 http://acm.nyist.net/JudgeOnline/problem.php?pid=305

    表达式求值 时间限制:3000 ms | 内存限制:65535 KB 难度:3 描述 Dr.Kong设计的机器人卡多掌握了加减法运算以后,最近又学会了一些简单的函数求值,比如,它知道函数min(20,23)的值是20 ,add(10,98) 的值是108等等.经过训练,Dr.Kong设计的机器人卡多甚至会计算一种嵌套的更复杂的表达式. 假设表达式可以简单定义为: 1. 一个正的十进制数 x 是一个表达式. 2. 如果 x 和 y 是 表达式,则 函数min(x,y )也是表达式,其值为x,y 中

  • FZU 2218 Simple String Problem(状态压缩DP)

    FZU 2218 Simple String Problem(状态压缩DP) tags : acm FZU 2218 Simple String Problem状态压缩DP 题意 解析 代码 组队赛时遇到的一道题,最后几分钟才做出来.说实话我做的时候也完全没有底,没想到竟然能一发AC 题意 给定一个长度为n,由字母表前k个字母组成的字符串.取其中的两个子串S2,S2,使得这两个字符串中没有相同的字符,求strlen(S1)*strlen(S2)的最大值. 解析 每个子串都可以得到一个01组成的"

  • C++数据结构学习:用栈做表达式求值

    栈的应用很广泛,原书只讲解了表达式求值,那我也就只写这些.其实,栈的最大的用途是解决回溯问题,这也包含了消解递归:而当你用栈解决回溯问题成了习惯的时候,你就很少想到用递归了,比如迷宫求解.另外,人的习惯也是先入为主的,比如树的遍历,从学的那天开始,就是递归算法,虽然书上也教了用栈实现的方法,但应用的时候,你首先想到的还是递归:当然了,如果语言本身不支持递归(如BASIC),那栈就是唯一的选择了--好像现在的高级语言都是支持递归的. 如下是表达式类的定义和实现,表达式可以是中缀表示也可以是后缀表示

Tags: