使用堆栈进行十进制到多基数的转换

介绍

在计算机科学中，我们经常进行数字转换，常见的数字系统包括二进制、八进制、十进制和十六进制。十进制是最常见的数字系统，因为它是人类使用的数字系统，但是对于计算机而言，二进制更加适合。在本文中，我们将介绍如何使用堆栈来将十进制转换为其他基数的数字系统。

什么是堆栈？

堆栈是计算机科学中的一种重要数据结构，它使用后进先出（Last-In-First-Out，LIFO）的原则来管理数据。这意味着最后进入堆栈的数据元素首先被访问。

下面是一段使用堆栈实现计算器的代码：

#include<bits/stdc++.h>
using namespace std;
int st[100000], top = 0;
void push(int x) {
    st[++top] = x;
}
int pop() {
    if (top == 0) {
        cout << "error: stack is empty" << endl;
        return -1;
    }
    return st[top--];
}
int main() {
    string s = "6 5 + 2 * 3 /";
    stringstream ss(s);
    string token;
    while (ss >> token) {
        if (token == "+") {
            int a = pop(), b = pop();
            push(a + b);
        } else if (token == "-") {
            int a = pop(), b = pop();
            push(b - a);
        } else if (token == "*") {
            int a = pop(), b = pop();
            push(a * b);
        } else if (token == "/") {
            int a = pop(), b = pop();
            push(b / a);
        } else {
            push(stoi(token));
        }
    }
    cout << pop() << endl;
    return 0;
}

在上面的代码中，我们首先定义了一个整型数组st和一个整型变量top，用来存储堆栈元素和记录堆栈顶部位置。其次，我们定义了两个函数push和pop，push函数将一个整数压入堆栈中，pop函数从堆栈中弹出一个元素并返回它的值。

最后，我们使用堆栈来实现一个反波兰式计算器。反波兰式是一种数学表达式的写法，其中所有运算符都在其操作数之后，而不是在它们之间。例如，6 5 + 2 * 3 /是一个反波兰式，其计算结果为4。

使用堆栈进行十进制到二进制转换

思路

将十进制数除以2并取余数，将余数依次压入堆栈中，直到商为0为止。然后弹出堆栈中的元素，得到二进制形式的数。

代码

#include<bits/stdc++.h>
using namespace std;
int st[100000], top = 0;
void push(int x) {
    st[++top] = x;
}
int pop() {
    if (top == 0) {
        cout << "error: stack is empty" << endl;
        return -1;
    }
    return st[top--];
}
int main() {
    int x;
    cin >> x;
    while (x > 0) {
        push(x % 2);
        x /= 2;
    }
    while (top > 0) {
        cout << pop();
    }
    cout << endl;
    return 0;
}

示例

输入：10

输出：1010

使用堆栈进行十进制到八进制转换

思路

将十进制数除以8并取余数，将余数依次压入堆栈中，直到商为0为止。然后弹出堆栈中的元素，得到八进制形式的数。

代码

#include<bits/stdc++.h>
using namespace std;
int st[100000], top = 0;
void push(int x) {
    st[++top] = x;
}
int pop() {
    if (top == 0) {
        cout << "error: stack is empty" << endl;
        return -1;
    }
    return st[top--];
}
int main() {
    int x;
    cin >> x;
    while (x > 0) {
        push(x % 8);
        x /= 8;
    }
    while (top > 0) {
        cout << pop();
    }
    cout << endl;
    return 0;
}

示例

输入：20

输出：24

使用堆栈进行十进制到十六进制转换

思路

将十进制数除以16并取余数，将余数依次压入堆栈中。将余数为10到15的元素用A到F表示。直到商为0为止。然后弹出堆栈中的元素，得到十六进制形式的数。

代码

#include<bits/stdc++.h>
using namespace std;
int st[100000], top = 0;
void push(int x) {
    st[++top] = x;
}
int pop() {
    if (top == 0) {
        cout << "error: stack is empty" << endl;
        return -1;
    }
    return st[top--];
}
string hex(int x) {
    if (x < 10) {
        return to_string(x);
    } else {
        return string(1, 'A' + (x - 10));
    }
}
int main() {
    int x;
    cin >> x;
    while (x > 0) {
        push(x % 16);
        x /= 16;
    }
    while (top > 0) {
        cout << hex(pop());
    }
    cout << endl;
    return 0;
}

示例

输入：255

输出：FF

总结

堆栈是一种非常有用的数据结构，它可以在许多计算机科学中使用。本文介绍了如何使用堆栈将十进制数转换为二进制、八进制和十六进制数。这些算法都非常简单，只需要进行除法和取余操作，然后将余数压入堆栈中。如果你对堆栈不熟悉，建议你自己动手写几个堆栈的问题，熟悉堆栈数据结构。