以下“输入顺序排序”都为先输入的先输出
一
输入：
一个乘法，乘法由两个加减法组成，两个加减法之间由括号相隔、或者没有相隔
保证每一个变量由一个字母（包括大小写）组成
若一个加减法由两个及以上个变量组成，则用括号括起来，如(a+b+c)
若只有一个正变量组成，则没有括号；如果是一个负变量，则有括号
例如该乘法可以是a(a+b+c)、(a+b+c)a、(a+b-c)(b-c+d)、aa、(-a+b)(-a)
其中左边为被乘数，如a、(a+b+c)、(a+b-c)、a、(-a+b)，右边为乘数，如(a+b+c)、a、(b-c+d)、a、(-a)
输出：
根据乘法分配律输出最终结果，分配成对的两个变量称之为对子，对子内部没有相隔，对子之间由加减'+'、'-'号隔开。
输出规则：
1. 对子内部的顺序为左边为被乘数所含的变量，右边为乘数所含的变量
2. 对子之间的顺序应该先由被乘数的输入顺序排序，相同被乘数再由乘数输入顺序排序。
3. 不处理一个对子是两个相同变量成对的情况，例如 aa
4. 不处理两个不同对子中变量相同的情况，例如 ab+ab+ba-ba
5. 如果第一个对子是正数，则不需要输出'+'；如果为负数则应该输出'-'
样例1:
输入
a(a+b+c)
输出
aa+ab+ac
样例2:
输入
(a+b+c)a
输出
aa+ba+ca
样例3:
输入
(a+b-c)(b-c+d)
输出
ab-ac+ad+bb-bc+bd-cb+cc-cd
样例4:
输入
(b-c+d)(a+b-c)
输出
ba+bb-bc-ca-cb+cc+da+db-dc
样例5:
输入
aa
输出
aa
思路：
维护三个队列，分别是被乘数、乘数、积
被乘数、乘数队列的数据为两个字符，分别代表正负符号和变量名
积的队列数据为一个字符和一个字符串，字符代表正负符号，字符串代表两个变量名相乘
循环被乘数内嵌乘数，积的正负符号等于被乘数与成熟符号的异或，积的字符串等于被乘数与乘数字符串相加
细节点：
- 输入要分别处理被乘数（i = 0不为左括号）、乘数（i = queue.length - 1不为右括号）为单个正变量情况
- 输入要处理括号内第一个字符是变量还是负号的情况
1 #include <iostream>
2 #include <queue>
3 #include <string>
4 #include <utility>
5
6 void Distribution (std::queue<std::pair<char,char> >,const std::queue<std::pair<char,char> >*,std::queue<std::pair<char,std::string> >*);
7 void print_ans (std::queue<std::pair<char,std::string> >);
8 void read_queue (std::queue<std::pair<char,char> >*,std::queue<std::pair<char,char> >*);
9 int main() {
10 std::queue<std::pair<char,char> > Multiplicand; // left variable, sign and variable
11 std::queue<std::pair<char,char> > Multiplier; // right variable, sign and variable
12 std::queue<std::pair<char,std::string> > ans;
13 read_queue(&Multiplicand,&Multiplier);
14 Distribution(Multiplicand,&Multiplier,&ans);
15 print_ans(ans);
16 return 0;
17 }
18 void read_queue (std::queue<std::pair<char,char> > *left,std::queue<std::pair<char,char> > *right) {
19 std::string input;
20 std:: cin >> input;
21 bool flag = false; // if flag == false, input left; else input right
22 for(int i = 0;i < input.length();i++) {
23 if(input[i] == ')') {
24 flag = true;
25 }
26 else if(input[i] == '(') { // first variable
27 i++;
28 if(input[i] != '-'){
29 if(!flag) // flag == false, input left
30 left->push(std::make_pair('+',input[i]));
31 else
32 right->push(std::make_pair('+',input[i]));
33 }
34 else{
35 i++;
36 if(!flag) // flag == false, input left
37 left->push(std::make_pair('-',input[i]));
38 else
39 right->push(std::make_pair('-',input[i]));
40 }
41 }
42 else if(i == 0) { // if left is single variable
43 flag = true;
44 left->push(std::make_pair('+',input[i]));
45 }
46 else if(i == (input.length() - 1)) { // if right is single variable
47 right->push(std::make_pair('+',input[i]));
48 }
49 else {
50 i++;
51 if(input[i - 1] == '+') {
52 if(!flag) // flag == false, input left
53 left->push(std::make_pair('+',input[i]));
54 else
55 right->push(std::make_pair('+',input[i]));
56 }
57 else {
58 if(!flag)
59 left->push(std::make_pair('-',input[i]));
60 else
61 right->push(std::make_pair('-',input[i]));
62 }
63 }
64 }
65 }
66 void Distribution(std::queue<std::pair<char,char> > left,const std::queue<std::pair<char,char> > *right,std::queue<std::pair<char,std::string> > *out) {
67 bool flag_left;
68 bool flag_right; // if flag == true, the sign of this variable is '-', else is '+'
69 std::string var_left; // for left variable
70 std::string var_right; //for right variable
71 std::queue<std::pair<char,char> > copy_right;
72 while(!left.empty()){
73 copy_right = *right; //initialization
74 if(left.front().first == '-'){
75 flag_left = true;
76 }
77 else{
78 flag_left = false;
79 }
80 var_left = left.front().second;
81 left.pop();
82 while(!copy_right.empty()){
83 if(copy_right.front().first == '-'){
84 flag_right = true;
85 }
86 else{
87 flag_right = false;
88 }
89 var_right = copy_right.front().second;
90 copy_right.pop();
91 if(flag_left ^ flag_right){ // xor is 0 means that '+', else is '-'
92 out->push(std::make_pair('-',var_left + var_right));
93 }
94 else {
95 out->push(std::make_pair('+',var_left + var_right));
96 }
97 }
98 }
99 }
100 void print_ans (std::queue<std::pair<char,std::string> > out){
101 char sign = out.front().first;
102 std::string var = out.front().second;
103 out.pop();
104 if(sign == '-'){
105 std::cout << '-';
106 }
107 std::cout << var;
108 while(!out.empty()){
109 sign = out.front().first;
110 var = out.front().second;
111 out.pop();
112 std::cout << sign << var;
113 }
114 std:: cout << std:: endl;
115 }
二
输入和输出同上述
注意同一个变量可能会输入多次
保证每一个变量由一个字母（包括大小写）组成
输出规则：
1. 对子内部的顺序由每个变量的输入顺序排序。假如b比a先输入过，即使a在被乘数中，a与b如果成对的话对子应该为 ba
2. 如果一个对子是两个相同变量成对，应该输出其次方形式，例如a*a的情况，则应该输出为 a^2 而不是aa
3. 不同对子顺序应该先由对子内左边的变量输入顺序排序，相同左边的变量之间再由右边的变量输入顺序排序。
如果为平方，则视为左边右边的变量都为该变量，例如a^2中，视为其左边与右边的变量都为a
4. 如果不同对子之间由相同两个变量成对，应该进行正常数学加减，数字与对子之间没有相隔，例如ab+ab+ab = 3ab。若数字为0则不输出该对子
5. 如果第一个对子是正数，则不需要输出'+'；如果为负数则应该输出'-'
样例1:
输入
a(a+b+c)
输出
a^2+ab+ac
Hint：变量输入顺序为a b c
样例2:
输入
(a+b+c)a
输出
a^2+ab+ac
Hint：变量输入顺序为a b c
样例3:
输入
(a+b-c)(b-c+d)
输出
ab-ac+ad+b^2-2bc+bd+c^2-cd
Hint：变量输入顺序为a b c d
样例4:
输入
(b-c+d)(a+b-c)
输出
b^2-2bc+bd+ba+c^2-cd-ca+da
Hint：变量输入顺序为b c d a
样例5:
输入
aa
输出
a^2
三
输入：
一个乘法，乘法由多个加减法组成。
输出同一、二
输出规则：
1. 对子内部的顺序由每个变量的输入顺序排序
2 若有多个相同变量成对，则应该展示其幂形式，例如 aaabbc则应该输出为 a^3b^2c
3.如果不同对子之间由相同两个变量成对，应该进行正常数学加减，数字与对子之间没有隔开，例如ab+ab+ab = 3ab。若数字为0则不输出该对子
4. 对子之间输出顺序：
设最左边的变量（不包括数字）为第一个变量，其右边的为第二个变量，以此类推；
如果变量中有次方，则应该根据次方规定其第n个变量，例如a^3b^2c中，第1~3个变量为a，第4~5个变量为b，第6个变量为c
先由第一个变量的输入顺序排序，第一个变量相同则由第二个变量输入顺序排序，以此类推;
5. 如果第一个对子是正数，则不需要输出'+'；如果为负数则应该输出'-'
样例1：
输入
(a+b-c)(b-c+d)
输出
ab-ac+ad+b^2-2bc+bd+c^2-cd
样例2：
输入
(a+b-c)*a*(b-c+d)
输出
a^2b-a^2c+a^2d+ab^2-2abc+abd+ac^2-acd
标签：std,right,变量,队列,queue,分配律,input,乘法,left From： https://www.cnblogs.com/zExNocs/p/16905372.html