数据结构中缀表达式求值

从键盘输入中缀表达式，建立操作数与运算符堆栈，计算并输出表达式的求值结果。
基本要求：实现 +, -, *, / 四个二元运算符以及（）；操作数范围为 0 至 9。
提高要求：实现 +, - 两个一元运算符（即正、负号）；操作数可为任意整型值（程序可不考虑计算溢出）。
若两个整数相除，结果只保留整数商（余数丢弃）；可不处理表达式语法错误。

栈与队列

采用 C ++ 的模板类，分别创建元素类型为整型的操作数栈 OPND 和字符型的运算符栈 OPTR，每个栈对象中，elem 指针用来建立长度为 n 的数组，n 表示栈中元素的最大个数，top 表示栈顶指针。

①中缀表达式以 ’#’ 结束，’#’ 字符也做运算符处理。
②'(‘、’)’ 作为运算符处理，括号内运算结束后需要消除括号。
③需要建立两个不同类型的栈，整型的操作数栈 OPND 和字符型的运算符栈 OPTR。
④算法主要步骤：
a. 初始时，OPND 置空，’#’ 作为 OPTR 栈底元素；
b. 依次读入表达式中的每个字符，若是操作数，直接压入 OPND 栈；
c. 若是运算符 (记为 θ)，PTR 栈顶运算符(为 λ) 优先级；
  λ<θ，θ 压入 OPTR 栈，继续读下一个字符；
  λ=θ，脱括号，继续读下一个字符；
  λ>θ，执行 λ 运算（λ 退栈），θ 等在栈外（不读下一个字符），即 θ 继续和 OPTR 栈顶运算符比较优先级（重复进行以上操作），直至 θ 能入栈。
⑤对于一元运算符（即正、负号），用 ’P’ 代表 ’+’，’N’ 代表 ’-‘。

#include<iostream>
using namespace std;
template <typename T>
class Stack                 // 模板类: 栈
{
public:
    Stack();                // 默认构造函数
    Stack(int n);           // 构造函数, 调用函数 createStack(int n), 创建长度为 n 的栈
    ~Stack();               // 虚构函数
    int createStack(int n); // 创建长度为 n 的栈
    int empty();            // 判断栈是否为空
    int full();             // 判断栈是否为满
    int push(T e);          // 将元素 e 压栈
    int pop(T &e);          // 元素出栈，保存在 e 中
    T get_top();            // 得到栈顶元素
    friend int isoperator(char &e);// 判断字符 e 是否为运算符
    friend int isp(char &e);// 返回栈中运算符的优先级
    friend int icp(char &e);// 返回栈外运算符的优先级
    friend int compute(int x, char a, int y);// 求值函数
private:
    T *elem;                // 建立长度为 n 的数组
    int n;                  // 栈中元素的最大个数
    int top;                // 栈顶指针
};
template<typename T>
Stack<T>::Stack()
{top = -1;}
template<typename T>
Stack<T>::Stack(int n)
{createStack(n);
}
template<typename T>
Stack<T>::~Stack()
{
    n = 0;
    top = -1;
    delete[]elem;}
template<typename T>
int Stack<T>::createStack(int n)
{if (n <= 0)
        return 0;
    this->n = n;
    top = -1;
    elem = new T[n];
    if (!elem)
        return 0;
    return 1;
}
template<typename T>
int Stack<T>::empty()
{return top == -1;}
template<typename T>
int Stack<T>::full()
{return top >= n - 1;}
template<typename T>
int Stack<T>::push(T e)
{if (top >= n - 1)
        return 0;
    elem[++top] = e;
    return 1;
}
template<typename T>
int Stack<T>::pop(T & e)
{if (top == -1)
        return 0;
    e = elem[top--];
    return 1;
}
template<typename T>
T Stack<T>::get_top()
{return elem[top];
};
int isoperator(char &e)        // 判断是否为运算符
{if (e == '+' || e == '-' || e == '*' || e == '/' || e == '(' || e == ')' || e == '#' || e == 'P' || e == 'N')
        return 1;      // 是运算符返回 1
    else
        return 0;      // 不是运算符返回 0
}
int isp(char &e)               // 返回栈中运算符的优先级
{switch (e)
    {
    case '#':
        return 0; break;
    case '(':
        return 1; break;
    case '+':
    case '-':
        return 2; break;
    case '*':
    case '/':
        return 3; break;
    case 'P':
    case 'N':
        return 4; break;
    case ')':
        return 5; break;
    default:
        return -1; break;
    }
}
int icp(char &e)                 // 返回栈外运算符的优先级
{switch (e)
    {
    case '#':
        return 0; break;
    case ')':
        return 1; break;
    case '+':
    case '-':
        return 2; break;
    case '*':
    case '/':
        return 3; break;
    case 'P':
    case 'N':
        return 4; break;
    case '(':
        return 5; break;
    default:
        return -1; break;
    }
}
int compute(int x, char a, int y)
{switch (a)
    {
    case '+':                // 计算加法
        return x + y; break;
    case '-':                // 计算减法
        return x - y; break;
    case '*':                // 计算乘法
        return x * y; break;
    case '/':                // 计算除法
        return x / y; break;
    default:
        return -1; break;
    }
}
int g1()
{
    char a, b, c;
    int i, j, f, value, firstOpnd, secondOpnd, m;
    Stack<char> OPTR(MAX);    // 建立运算符栈
    Stack<int> OPND(MAX);     // 建立操作数栈
    OPTR.push('#');           //'#' 压栈
    cout << "请输入中缀表达式：";
    a = getchar();
    while (a != '#' || OPTR.get_top() != '#')
    {if (!isoperator(a))   // 不是运算符，即为操作数，操作数入栈
            OPND.push(a - 48);// 将字符型转化为整型数字
        else                  // 是运算符，与栈顶运算符比较优先级大小
        {b = OPTR.get_top();// 得到栈顶元素
            i = isp(b);       // 栈顶运算符的优先级
            j = icp(a);       // 栈外运算符的优先级
            if (i < j)        // 栈外运算符优先级高，运算符入栈
                OPTR.push(a);
            else
            {OPTR.pop(b);                    
                if (b != '('&&i == j || i > j)
                {c = OPTR.get_top();
                    if ((c == '(' || c == '#') && (b == 'P' || b == 'N'))    /* c 为一元运
                                                                            算符：正负号 */
                    {OPND.pop(firstOpnd); // 得到操作数
                        switch (b)
                        {
                        case 'P':            // 正号
                            f = firstOpnd * 1;
                            break;
                        case 'N':            // 负号
                            f = firstOpnd * (-1);
                            break;
                        }
                    }
                    else                     // c 为二元运算符
                    {OPND.pop(secondOpnd); // 得到第二操作数
                        OPND.pop(firstOpnd);  // 得到第一操作数
                        f = compute(firstOpnd, b, secondOpnd); // 计算求值
                    }
                    OPND.push(f);             // 求值结果压栈
                    continue;
                }
            }
        }
        c = a;
        a = getchar();                         // 继续读取字符
        while(!isoperator(a) && !isoperator(c))  /* 若连续读取字符均为数字，则乘以位权
                                                  得到多位数 */
        {OPND.pop(m);
            m = m * 10 + a - 48;
            OPND.push(m);
            c = a;
            a = getchar();}
        
    }
    OPND.pop(value);
    return value;      // 返回表达式的结果
}
int main()
{
    int a;
    a = g1();
    cout << "运算结果为:" << a << endl;
    return 0;
}

（1）程序输入：3+5*(9-5)/10#
程序输出：5

（2）程序输入：P9+10*(N2*8/4)-10#
程序输出：-41

（3）程序输入：20-3*25+(N41/3)*100#
程序输出：-1355

数据结构中缀表达式求值

题目要求

涉及知识点

数据结构设计

算法描述

程序代码

示例