顺序栈的实践应用之 进制转换+后缀表达式（c语言版）

目录

一：进制转换

二：后缀表达式

一：进制转换

本题要求实现十进制转R（R<10 && R>0）进制。

 要求：

#include
#include
typedef int Status;
typedef int SElemType;
#define stack_INIT_SIZE     100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
 typedef struct {
       SElemType  *base;   //栈底指针
       SElemType  *top;     //栈顶指针
       int stacksize;       //栈空间
}Sqstack;
Sqstack S;
Status iniStack(Sqstack &S);
Status push(Sqstack &S,SElemType x);
Status pop(Sqstack &S,SElemType &e);
void conversion(int n,int R);
int main()
{
    int N,R;
    scanf("%d",&N);  //输入十进制数
    scanf("%d",&R);  //输入要转换的进制
    if(R<0||R>=10)  //判断R是否合法
    {
        printf("illegal input");
        return ERROR;
    }
    //printf("开始");
    conversion(N,R);  //进制转换
    return OK;
}

Status iniStack(Sqstack &S){
    S.base = (SElemType*)malloc(stack_INIT_SIZE*sizeof(SElemType));
//    if(!S.base) exit(OVERFLOW);
    S.top =S.base;
    S.stacksize=stack_INIT_SIZE;              
}
Status push(Sqstack &S,SElemType x){
    if(S.base-S.top==stack_INIT_SIZE)
        return ERROR;
    *S.top++=x;
    return OK;
}
Status pop(Sqstack &S,SElemType &e){
    if(S.base==S.top)
        return ERROR;
    e=*--S.top;
    return OK;
}
bool StackEmpty(Sqstack &S)
{
    if (S.top == S.base) return false;
    return true;
}
void conversion(int n,int R){
    int e;Sqstack S;
    iniStack(S);
//    printf("开始");
    //printf("%d",n);
    while(n>=R){
        push(S,n%R);
        n/=R;
        //printf("%d",n);
    }
    push(S,n);
   // printf("push结束");
    while(S.base!=S.top){
        pop(S,e);
        printf("%d",e);
    }
}

二：后缀表达式

        后缀表达式，又称逆波兰式，指的是不包含括号，运算符放在两个运算对象的后面，所有的计算按运算符出现的顺序，严格从左向右进行。

请编程实现后缀表达式求值，运算符仅有+、-、*、/ 四种，运算符和操作数之间用空格分隔，例如：12 8 5 - /，后缀表达式总长度不超过300000。

#include
#include
#include
using namespace std;
typedef int Status;
typedef int SElemType;
#define stack_INIT_SIZE     3000000
#define stackINCREMENT  10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
 typedef struct {
      long long int  *base;   //栈底指针
      long long  int  *top;     //栈顶指针
       int stacksize;       //栈空间
}Sqstack;
Sqstack S;
Status iniStack(Sqstack &S){
    S.base = (long long int*)malloc(stack_INIT_SIZE*sizeof(long long int));
//    if(!S.base) exit(OVERFLOW);
    S.top =S.base;
    S.stacksize=stack_INIT_SIZE;              
}
Status push(Sqstack &S,long long int x){
    if(S.base-S.top==stack_INIT_SIZE)
        return ERROR;
    *S.top++=x;
    return OK;
}
Status pop(Sqstack &S,long long int &e){
    if(S.base==S.top)
        return ERROR;
    e=*--S.top;
    return OK;
}
bool StackEmpty(Sqstack &S)
{
    if (S.top == S.base) return false;
    return true;
}
void conversion(int n,int R){
    long long int e;Sqstack S;
    iniStack(S);
//    printf("开始");
    //printf("%d",n);
    while(n>=R){
        push(S,n%R);
        n/=R;
        //printf("%d",n);
    }
    push(S,n);
   // printf("push结束");
    while(S.base!=S.top){
        pop(S,e);
        printf("%d",e);
    }
}

int A(char* str)
{
    int i = 0;
    Sqstack Numbers;
    iniStack(Numbers);
    SElemType number_to_push;
    long long int num1, num2;
    while (str[i] != '') {
        if (str[i] != ' ') {
            if (str[i] >= '0' && str[i] <= '9') {
                number_to_push = 0;
                while (str[i] != ' ' && str[i]) {
                    number_to_push = number_to_push * 10 + (str[i] - '0');
                    i++;
                }
                push(Numbers, number_to_push);
            } else {
                pop(Numbers, num2);
                pop(Numbers, num1);
                switch (str[i]) {
                case '+': {
                    num1 += num2;
                    break;
                }
                case '-': {
                    num1 -= num2;
                    break;
                }
                case '*': {
                    num1 *= num2;
                    num1=num1%1000000007;
                    break;
                }
                case '/': {
                    num1 /= num2;
                    break;
                }
                case '%': {
                    num1 %= num2;
                    break;
                }
                }
                push(Numbers, num1%1000000007);
            }
        }
        i++;
    }
    pop(Numbers, num1);
    return num1;
}
int main(){
        Sqstack S;
        iniStack(S);
        int num1;
        char num[300000];
//        scanf("%s",&num);
        cin.getline(num,300000);
//        printf("%s",num);
        num1=A(num);
        printf("%d",num1);
}