使用栈求 中缀/后缀/前缀 表达式的代码

目录

• 使用栈求中缀表达式的值的方法:
• 使用栈求后缀表达式的方法
• 使用栈求前缀表达式的方法

使用栈求中缀表达式的值的方法:

将数字存入一栈, 运算符存入另一栈. 入栈的运算符必须大于栈顶运算符的优先级才能入栈, 小于等于均将栈顶运算符出栈后计算处理. 如图作a(值为4)*=b(值为5)从而得到a的值为20. 左括号类比栈底处理, 右括号类比原数组循环结束后, 排空运算符堆栈的操作. 实现代码如下(参考天勤代码):

#include <iostream>
#include <cmath>
using namespace std;

const int maxSize = 14;
const float Min = 1e-3;

int getPriority(char op)
{
    switch (op)
    {
    case '+':
    case '-':
        return 0;
    case '*':
    case '/':
        return 1;
    }
}

int calSub(float num1, char op, float num2, float &result)
{
    switch (op)
    {
    case '/':
        if (fabs(num2) < Min)
            return 0;
        else
            result = num1 / num2;
        break;
    case '*':
        result = num1 * num2;
        break;
    case '+':
        result = num1 + num2;
        break;
    case '-':
        result = num1 - num2;
    }
    return 1;
}

int calTopTwo(float s1[], int &top1, char s2[], int &top2)
{
    float num1, num2, result;
    num2 = s1[top1--];
    num1 = s1[top1--];
    char op = s2[top2--];
    int flag = calSub(num1, op, num2, result);
    if (flag == 0)
    {
        cout << "Error";
    }
    s1[++top1] = result;
    return flag;
}

float calInfix(char exp[])
{
    float s1[maxSize];
    int top1 = -1;
    char s2[maxSize];
    int top2 = -1;
    int i = 0;
    while (exp[i] != '\0')
    {
        if ('0' <= exp[i] && exp[i] <= '9')
        {
            s1[++top1] = exp[i] - '0';
            i++;
        }
        else if (exp[i] == '(')
        {
            s2[++top2] = '(';
            i++;
        }
        else if (exp[i] == '+' ||
                 exp[i] == '-' ||
                 exp[i] == '*' ||
                 exp[i] == '/')
        {
            if (top2 == -1 ||
                s2[top2] == '(' ||
                getPriority(exp[i]) > getPriority(s2[top2]))
            {
                s2[++top2] = exp[i];
                i++;
            }
            else
            {
                int flag = calTopTwo(s1, top1, s2, top2);
                if (flag == 0)
                    return 0;
            }
        }
        else if (exp[i] == ')')
        {
            while (s2[top2] != '(')
            {
                int flag = calTopTwo(s1, top1, s2, top2);
                if (flag == 0)
                    return 0;
            }
            i++;
            top2--;
        }
    }
    while (top2 != -1)
    {
        int flag = calTopTwo(s1, top1, s2, top2);
        if (flag == 0)
            return 0;
    }
    return s1[0];
}
int main()
{
    char s1[14] = "1+2/4*(3+5*6)";
    cout << calInfix(s1) << endl;
    return 0;
}
/*结果
17.5
*/

使用栈求后缀表达式的方法

将数字和运算符均依次存入栈中, 在压入运算符时, 将栈顶两数字与运算符进行运算, 得到新数字并存回栈中(注意运算次序, 先入栈的在左, 栈顶在右). 具体过程参考此处 代码如下(自己写的野生代码):

#include <iostream>
using namespace std;
const int maxSize = 16;
const float Min = 1e-8;
float calPostFix(char exp[])
{
    float s[maxSize];
    int top = -1, i = 0;
    while (exp[i] != '\0')
    {
        if ('0' <= exp[i] && exp[i] <= '9')
        {
            s[++top] = exp[i++]-'0';
        }
        else
        {
            switch (exp[i++])
            {
            case '+':
                s[--top] += s[top];
                break;
            case '-':
                s[--top] -= s[top];
                break;
            case '*':
                s[--top] *= s[top];
                break;
            case '/':
                if (s[top] < Min)
                {
                    cout << "Error";
                    return 0;
                }
                s[--top] /= s[top];
            }
        }
    }
    return s[0];
}
int main()
{
    char s[maxSize] = {'1', '2', '+', '5', '*'};
    cout << calPostFix(s);
}
/*结果
15
*/

使用栈求前缀表达式的方法

此处求前缀表达式和后缀表达式的方法相似. 此处从右到左扫描, 在栈顶两数字顺序是先入栈在右, 栈顶在左

#include <iostream>
using namespace std;
const int maxSize = 16;
const float Min = 1e-8;
float calPreFix(char exp[], int len)
{
    float s[maxSize];
    int top = -1, i = len - 1;
    while (i >= 0)
    {
        if ('0' <= exp[i] && exp[i] <= '9')
        {
            s[++top] = exp[i--] - '0';
        }
        else
        {
            switch (exp[i--])
            {
            case '+':
                s[--top] = s[top] + s[top - 1];
                break;
            case '-':
                s[--top] = s[top] - s[top - 1];
                break;
            case '*':
                s[--top] = s[top] * s[top - 1];
                break;
            case '/':
                if (s[top - 1] < Min)
                {
                    cout << "Error";
                    return 0;
                }
                s[--top] = s[top] / s[top - 1];
            }
        }
    }
    return s[0];
}
int main()
{
    char s[maxSize] = {'+', '3', '*', '4',
                       '*', '5', '+', '2', '3'};
    cout << calPreFix(s, 9);
}
/*结果
103
*/