表达式的三种表示方法

设  Exp = S1   OP   S2

  • OP  S1   S2      为前缀表示法
  • S1   OP  S2      为中缀表示法
  •  S1   S2   OP     为后缀表示法

前缀式的运算规则为:

连续出现的两个操作数和在它们之前且紧靠它们的一个运算符构成一个最小表达式;

后缀式的运算规则为:

连续出现的两个操作数和在它们之后且紧靠它们的一个运算符构成一个最小表达式;

利用栈从后缀式求值

原理：遇到运算数则入栈，遇到操作符则出栈2个数，计算，结果入栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
#include <iostream>

using namespace std;
class steak;
class StackNode
{
    friend class LinkedStack;

public:
    StackNode* link;
    double data;

public:
    StackNode(StackNode* ptr = NULL)
    {
        link = ptr;
    }
    StackNode(double& c, StackNode* ptr = NULL)
    {
        data = c;
        link = ptr;
    }
};
class LinkedStack
{ //链式栈类定义
public:
    StackNode* top; //栈顶指针
public:
    LinkedStack(); //构造函数

    void Push(double& ch); //进栈
    int Pop(double& ch);   //退栈
    void makeEmpty();      //清空栈的内容
    int IsEmpty() { return (top == NULL) ? 1 : 0; }
};
LinkedStack::LinkedStack()
{
    top = NULL;
}
void LinkedStack::makeEmpty()
{
    if (top != NULL)
    {
        StackNode* p = top->link;
        while (top != NULL)
        { //逐个结点释放
            p = top;
            top = top->link;
            delete p;
        }
    }
}
void LinkedStack::Push(double& ch)
{
    top = new StackNode(ch, top); //创建新结点
}

int LinkedStack::Pop(double& ch)
{
    //删除栈顶结点, 返回被删栈顶元素的值。
    if (IsEmpty())
        return 0;       //栈空返回
    StackNode* p = top; //暂存栈顶元素
    top = top->link;    //退栈顶指针
    ch = p->data;
    delete p; //释放结点
    return 1;
}

class Calculator
{
public:
    Calculator() {};
    void Run();
    //执行表达式计算；类似于主程序:输入数字和操作符，若数字则调用AddOperand；符号则调用DoOperator；
    void Clear();

private:
    LinkedStack S;
    void AddOperand(double value); //操作数进栈
    int Get2Operands(double& left, double& right);
    //从操作数栈中取出两个操作数
    void DoOperator(char op);
    //pop出两个操作数(Get2Operands)，进行op 计算，将计算结果入栈(AddOperand)
};
void Calculator::AddOperand(double value)
{
    S.Push(value);
};
void Calculator::Clear()
{
    S.makeEmpty();
};
int Calculator::Get2Operands(double& left, double& right)
{
    if (S.IsEmpty())
    {
        cout << "缺少右操作数!" << endl;
        return 0;
    }
    S.Pop(right);
    if (S.IsEmpty())
    {
        cout << "缺少左操作数!" << endl;
        return 0;
    }
    S.Pop(left);
    return 1;
};
void Calculator::Run()
{
    char ch;
    double newoperand;
    while (cin>>ch, ch != '#') // #输入结束符号
    {
        if (ch != ' ') {
            if (ch == '+'  ch == '-'  ch == '*'  ch == '/')
            {
                DoOperator(ch);
            }
            else
            {
                cin.putback(ch);        //回退一下，
                cin >> newoperand;      //读取操作数
                AddOperand(newoperand); //加入到操作数栈
            }
        }
    }
    S.Pop(newoperand);
    cout << newoperand; //输出计算结果
};
void Calculator::DoOperator(char op)
{
    double left, right, value;
    if (Get2Operands(left, right))
    {
        if (op == '+')
        {
            value = left + right;
            S.Push(value);
        }
        else if (op == '-')
        {
            value = left - right;
            S.Push(value);
        }
        else if (op == '*')
        {
            value = left * right;
            S.Push(value);
        }
        else
        {
            if (right == 0.0)
            {
                cerr << "Divide by 0 !" << endl;
                Clear();
            }
            else
            {
                value = left / right;
                S.Push(value);
            }
        }
    }
    else
        Clear();
};
int main()
{
    Calculator CALC;
    CALC.Run();
    return 0;
}