以下“输入顺序排序”都为先输入的先输出
一
输入：
一个乘法，乘法由两个加减法组成，两个加减法之间由括号相隔、或者没有相隔
保证每一个变量由一个字母（包括大小写）组成
若一个加减法由两个及以上个变量组成，则用括号括起来，如(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 #define cout std::cout 7 #define cin std::cin 8 #define endl std::endl 9 10 typedef std::queue<std::pair<char,char> > pair_char; 11 typedef std::queue<std::pair<char,std::string> > pair_string; 12 13 void read_queue (pair_char*,pair_char*); 14 void Distribution (pair_char,const pair_char*,pair_string*); 15 void print_ans (pair_string); 16 int main() { 17 pair_char Multiplicand; // left variable, sign and variable 18 pair_char Multiplier; // right variable, sign and variable 19 pair_string ans; 20 read_queue(&Multiplicand,&Multiplier); 21 Distribution(Multiplicand,&Multiplier,&ans); 22 print_ans(ans); 23 return 0; 24 } 25 void read_queue (pair_char* left,pair_char* right) { 26 std::string input; 27 cin >> input; 28 bool flag = false; // if flag == false, input left; else input right 29 for(int i = 0;i < input.length();i++) { 30 if(input[i] == ')') { 31 flag = true; 32 } 33 else if(input[i] == '(') { // first variable 34 i++; 35 if(input[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 else{ 42 i++; 43 if(!flag) // flag == false, input left 44 left->push(std::make_pair('-',input[i])); 45 else 46 right->push(std::make_pair('-',input[i])); 47 } 48 } 49 else if(i == 0) { // if left is single variable 50 flag = true; 51 left->push(std::make_pair('+',input[i])); 52 } 53 else if(i == (input.length() - 1)) { // if right is single variable 54 right->push(std::make_pair('+',input[i])); 55 } 56 else { 57 i++; 58 if(input[i - 1] == '+') { 59 if(!flag) // flag == false, input left 60 left->push(std::make_pair('+',input[i])); 61 else 62 right->push(std::make_pair('+',input[i])); 63 } 64 else { 65 if(!flag) 66 left->push(std::make_pair('-',input[i])); 67 else 68 right->push(std::make_pair('-',input[i])); 69 } 70 } 71 } 72 } 73 void Distribution(pair_char left,const pair_char* right,pair_string *out) { 74 bool flag_left; 75 bool flag_right; // if flag == true, the sign of this variable is '-', else is '+' 76 std::string var_left; // for left variable 77 std::string var_right; //for right variable 78 pair_char copy_right; 79 80 while(!left.empty()){ 81 copy_right = *right; //initialization 82 if(left.front().first == '-'){ 83 flag_left = true; 84 } 85 else{ 86 flag_left = false; 87 } 88 var_left = left.front().second; 89 left.pop(); 90 while(!copy_right.empty()){ 91 if(copy_right.front().first == '-'){ 92 flag_right = true; 93 } 94 else{ 95 flag_right = false; 96 } 97 var_right = copy_right.front().second; 98 copy_right.pop(); 99 if(flag_left ^ flag_right){ // xor is 0 means that '+', else is '-' 100 out->push(std::make_pair('-',var_left + var_right)); 101 } 102 else { 103 out->push(std::make_pair('+',var_left + var_right)); 104 } 105 } 106 } 107 } 108 void print_ans (pair_string out){ 109 char sign = out.front().first; 110 std::string var = out.front().second; 111 out.pop(); 112 if(sign == '-'){ 113 cout << '-'; 114 } 115 cout << var; 116 while(!out.empty()){ 117 sign = out.front().first; 118 var = out.front().second; 119 out.pop(); 120 cout << sign << var; 121 } 122 cout << endl; 123 }
二
输入和输出同上述
注意同一个变量可能会输入多次
保证每一个变量由一个字母（包括大小写）组成
输出规则：
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
转载请注明原文链接：队列的应用 乘法分配律