利用順序棧實作基本算術運算——C語言

/***************順序棧的運算**************
*********将中綴表達式轉化為字尾表達式******
*利用棧的特性進行含有+，-*，/的整型算術運算*/
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define N 30
int stack_num[N]; //運算數堆棧
char stack_opr[N]; //運算符堆棧
int top_1 = 0; //運算數堆頂
int top_0 = 0; //運算符棧頂
void make_empty(int);
bool is_empty(int);
bool is_full(int);
void push(int, int);
int pop(int);
int deal(char);
char class(char);
void process(char);
int main(void)
{
    char ch;
    make_empty(1);
    make_empty(0);
    while (1) {
        printf("輸入一個整型表達式，如123*+=或者(1+2*3/4)-1=\n表達式:");
        while (1) {
            scanf("%c", &ch);
            if (ch != ' ') {
                if (ch >= '0' && ch <= '9')    //運算數進入運算數棧
                    push(ch - '0', 1);
                else if (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '(' || ch == ')')
                    process(ch);                   //運算符進入運算符棧
                else if (ch == '=') {
                    process(ch);
                    break;
                } //else if (ch == '\n')
                //    break;
                else {
                    printf("非法輸入字元!\n");
                    break;
                }
            }
        }
        while (getchar() != '\n')//去掉換行鍵對下一次輸入的影響
            ;
        if (top_1 == 1)
            printf("答案是:%d\n", stack_num[top_1 - 1]);
        else
            printf("非法表達式!\n");
        make_empty(1);
        make_empty(0);
    }
    return 0;
}
void make_empty(int a) //置空棧
{
    if (a)
        top_1 = 0;
    else
        top_0 = 0;
}
bool is_empty(int a) //判斷是否空棧
{
    if (a)
        return top_1 == 0;
    else
        return top_0 == 0;
}
bool is_full(int a) //判斷是否滿棧
{
    if (a)
        return top_1 == N;
    else
        return top_0 == N;
}
void push(int x, int a) //入棧
{
    if (is_full(a)) {
        printf("堆棧上溢!\n");
        exit(0);
    }
    if (a)
        stack_num[top_1++] = x;
    else
        stack_opr[top_0++] = x;
}
int pop(int a) //出棧
{
    if (is_empty(a)) {
        printf("堆棧下溢!\n");
        exit(0);
    }
    if (a)
        return stack_num[--top_1];
    else
        return stack_opr[--top_0];
}
int deal(char ch) //算術運算
{
    int a, b;
    switch (ch) {
    case '+':
        a = pop(1);
        b = pop(1);
        return a + b;
    case '-':
        a = pop(1);
        b = pop(1);
        return b - a; //注意順序
    case '/':
        a = pop(1);
        b = pop(1);
        return b / a; //注意順序
    case '*':
        a = pop(1);
        b = pop(1);
        return a * b;
    default:
        printf("非法輸入2!");
        exit(0);
    }
}
char class(char ch) //使+，-以及/，*的優先級分别一樣
{
    if (ch == '/')
        return '*';
    else if (ch == '-')
        return '+';
    else
        return ch;
}
void process(char ch) //運算過程優先級處理
{
    if (is_empty(0)) //運算符棧為空直接壓入
        push(ch, 0);
    else {
        if (ch == '=') //遇到‘=’全部出棧，計算結果
            while (!is_empty(0)) {
                push(deal(pop(0)), 1);
            }
        else if (ch == ')') { //遇到‘)’壓出堆棧内容直到‘(’
            while (stack_opr[top_0 - 1] != '(')
                push(deal(pop(0)), 1);
            pop(0);
        } else if (class(ch) < class(stack_opr[top_0 - 1])) //運算符堆棧隻能按優先級從小到大排列
            push(ch, 0); //‘(’是例外,特殊處理
        else {
            while (class(ch) >= class(stack_opr[top_0 - 1]) && top_0 && stack_opr[top_0 - 1] != '(')
                push(deal(pop(0)), 1); //‘(’隻能由大括号壓出
            push(ch, 0);
        }
    }
}
           

運作結果