使用堆栈添加到非常大的数字
Adding to very large numbers using stack
我是 C++ 的新手,我试图编写这个程序来使用字符串将两个非常大的数字相加,但该程序无法正常工作,我无法理解它有什么问题,请帮助我解决这个问题.
#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main() {
stack <char> a1;
stack<char> a2;
stack<int> result;
stack<int> temp;
int carry = 0;
string num1;
string num2;
cout << "Enter first number (both numbers should have equal digits)" << endl;
getline(cin, num1);
cout << "Enter second number" << endl;
getline(cin, num2);
for (int i = num1.size()-1; i >= 0; i--) {
a1.push(num1[i]);
a2.push(num2[i]);
}
while (!a1.empty() && !a2.empty()) {
int element = (int)a1.top() + (int)a2.top() + carry;
cout << element;
if (element > 10) {
element %= 10;
carry = 1;
}
result.push(element);
cout << result.top() << endl;
a1.pop();
a2.pop();
}
string abc;
while (!result.empty()) {
temp.push(result.top());
result.pop();
abc += temp.top();
}
cout << abc;
}
我知道我肯定犯了一个逻辑错误,但我无法理解,谁能指导我?
以下是我得到的输出
我在想,为什么要用栈呢。我的猜测是你这样做了,因为数字必须从右到左处理。
此外,您在使用不同长度的字符串时遇到了明显的挑战。
但这两个问题都可以轻松解决。让我们从不同长度的字符串开始。
如果 2 个字符串的长度不同,我们可以用前导“0”填充(填充)较短的字符串。我们需要添加多少个前导“0”?对,长度的增量。
为了在字符串中的某个位置插入字符,我们有函数insert。
因此,其代码如下所示:
if (numberAsString1.length() < numberAsString2.length())
numberAsString1.insert(0, numberAsString2.length() - numberAsString2.length(), '0');
else
numberAsString2.insert(0, numberAsString1.length() - numberAsString2.length(), '0');
这很简单。
结果将始终是 2 个长度相等的字符串。输入“1234”和“9”,我们将得到:“1234”和“0009”。
这使下一个任务更容易。
现在我们有 2 个等长的字符串,我们可以像在学校学到的那样“相加”。
我们从右到左,从字符串中字符的最高可能索引开始。这总是长度为 1。
为了计算和,我们需要先从字符串中的字符中减去'0'的ASCII码,因为字符串中包含的不是整数,而是字符。例如“123”由“1”、“2”、“3”组成,而不是由 1、2、3 组成。
总结起来很简单:数字+数字+进位。
结果数字总是 sum % 10
。下一个进位总是 sum / 10
。示例 1:3+5=8 8%10=8 8/10=0
。示例 2:9+8=17 17%10=7 17/10=1
.
所以,这也很简单。
在我们对字符串的所有数字进行处理后,可能仍然存在一组进位。然后我们将其添加到字符串中。
在任何情况下都可以使用 instert 函数添加数字。因为我们想在结果字符串的左侧插入数字。
因此,从右到左工作,使用正确的索引和插入函数,我们不需要堆栈。
通过大量的输入检查,整个函数看起来像这样:
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
int main() {
// Give instruction to user
std::cout << "\nPlease enter 2 positive interger numbers:\n";
// Here we will store the user input
std::string numberAsString1{}, numberAsString2{};
// Get strings from user and check, if that worked
if (std::cin >> numberAsString1 >> numberAsString2) {
// Check if all characters in string 1 are digits
if (std::all_of(numberAsString1.begin(), numberAsString1.end(), std::isdigit)) {
// Check if all characters in string 2 are digits
if (std::all_of(numberAsString2.begin(), numberAsString2.end(), std::isdigit)) {
// ---------------------------------------------------------------------------------
// Here we will store the calculated result
std::string result{};
// Temporary helpers
unsigned int carry{};
// ---------------------------------------------------------------------------------
// Make strings equal length. Pad with leading '0' s
if (numberAsString1.length() < numberAsString2.length())
numberAsString1.insert(0, numberAsString2.length() - numberAsString2.length(), '0');
else
numberAsString2.insert(0, numberAsString1.length() - numberAsString2.length(), '0');
// ---------------------------------------------------------------------------------
// Iterate over all digits from right to left
for (int i = numberAsString1.length()-1; i >= 0; --i) {
// Calculate the sum
const int sum = numberAsString1[i]-'0' + numberAsString2[i] - '0' + carry;
// Get the carry bit in case of overflow
carry = sum / 10;
// Save the resulting digit
result.insert(0, 1, sum % 10 + '0');
}
// handle last carry bit
if (carry) result.insert(0, 1, '1');
// ---------------------------------------------------------------------------------
// Show result
std::cout << "\n\nSum: " << result << '\n';
}
else std::cerr << "\n\nError: number 1 contains illegal characters\n";
}
else std::cerr << "\n\nError: number 2 contains illegal characters\n";
}
else std::cerr << "\n\nError: Problem with input\n";
return 0;
}
我是 C++ 的新手,我试图编写这个程序来使用字符串将两个非常大的数字相加,但该程序无法正常工作,我无法理解它有什么问题,请帮助我解决这个问题.
#include<iostream>
#include<stack>
#include<string>
using namespace std;
int main() {
stack <char> a1;
stack<char> a2;
stack<int> result;
stack<int> temp;
int carry = 0;
string num1;
string num2;
cout << "Enter first number (both numbers should have equal digits)" << endl;
getline(cin, num1);
cout << "Enter second number" << endl;
getline(cin, num2);
for (int i = num1.size()-1; i >= 0; i--) {
a1.push(num1[i]);
a2.push(num2[i]);
}
while (!a1.empty() && !a2.empty()) {
int element = (int)a1.top() + (int)a2.top() + carry;
cout << element;
if (element > 10) {
element %= 10;
carry = 1;
}
result.push(element);
cout << result.top() << endl;
a1.pop();
a2.pop();
}
string abc;
while (!result.empty()) {
temp.push(result.top());
result.pop();
abc += temp.top();
}
cout << abc;
}
我知道我肯定犯了一个逻辑错误,但我无法理解,谁能指导我? 以下是我得到的输出
我在想,为什么要用栈呢。我的猜测是你这样做了,因为数字必须从右到左处理。
此外,您在使用不同长度的字符串时遇到了明显的挑战。
但这两个问题都可以轻松解决。让我们从不同长度的字符串开始。
如果 2 个字符串的长度不同,我们可以用前导“0”填充(填充)较短的字符串。我们需要添加多少个前导“0”?对,长度的增量。
为了在字符串中的某个位置插入字符,我们有函数insert。
因此,其代码如下所示:
if (numberAsString1.length() < numberAsString2.length())
numberAsString1.insert(0, numberAsString2.length() - numberAsString2.length(), '0');
else
numberAsString2.insert(0, numberAsString1.length() - numberAsString2.length(), '0');
这很简单。
结果将始终是 2 个长度相等的字符串。输入“1234”和“9”,我们将得到:“1234”和“0009”。
这使下一个任务更容易。
现在我们有 2 个等长的字符串,我们可以像在学校学到的那样“相加”。
我们从右到左,从字符串中字符的最高可能索引开始。这总是长度为 1。
为了计算和,我们需要先从字符串中的字符中减去'0'的ASCII码,因为字符串中包含的不是整数,而是字符。例如“123”由“1”、“2”、“3”组成,而不是由 1、2、3 组成。
总结起来很简单:数字+数字+进位。
结果数字总是 sum % 10
。下一个进位总是 sum / 10
。示例 1:3+5=8 8%10=8 8/10=0
。示例 2:9+8=17 17%10=7 17/10=1
.
所以,这也很简单。
在我们对字符串的所有数字进行处理后,可能仍然存在一组进位。然后我们将其添加到字符串中。
在任何情况下都可以使用 instert 函数添加数字。因为我们想在结果字符串的左侧插入数字。
因此,从右到左工作,使用正确的索引和插入函数,我们不需要堆栈。
通过大量的输入检查,整个函数看起来像这样:
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
int main() {
// Give instruction to user
std::cout << "\nPlease enter 2 positive interger numbers:\n";
// Here we will store the user input
std::string numberAsString1{}, numberAsString2{};
// Get strings from user and check, if that worked
if (std::cin >> numberAsString1 >> numberAsString2) {
// Check if all characters in string 1 are digits
if (std::all_of(numberAsString1.begin(), numberAsString1.end(), std::isdigit)) {
// Check if all characters in string 2 are digits
if (std::all_of(numberAsString2.begin(), numberAsString2.end(), std::isdigit)) {
// ---------------------------------------------------------------------------------
// Here we will store the calculated result
std::string result{};
// Temporary helpers
unsigned int carry{};
// ---------------------------------------------------------------------------------
// Make strings equal length. Pad with leading '0' s
if (numberAsString1.length() < numberAsString2.length())
numberAsString1.insert(0, numberAsString2.length() - numberAsString2.length(), '0');
else
numberAsString2.insert(0, numberAsString1.length() - numberAsString2.length(), '0');
// ---------------------------------------------------------------------------------
// Iterate over all digits from right to left
for (int i = numberAsString1.length()-1; i >= 0; --i) {
// Calculate the sum
const int sum = numberAsString1[i]-'0' + numberAsString2[i] - '0' + carry;
// Get the carry bit in case of overflow
carry = sum / 10;
// Save the resulting digit
result.insert(0, 1, sum % 10 + '0');
}
// handle last carry bit
if (carry) result.insert(0, 1, '1');
// ---------------------------------------------------------------------------------
// Show result
std::cout << "\n\nSum: " << result << '\n';
}
else std::cerr << "\n\nError: number 1 contains illegal characters\n";
}
else std::cerr << "\n\nError: number 2 contains illegal characters\n";
}
else std::cerr << "\n\nError: Problem with input\n";
return 0;
}