如何使用堆疊來計算後序式?

Question

小弟才剛剛學DELPHI不久有個問題想請教各位高手...
就是學校的老師出了個作業，是一個算式，但是必須使用堆疊的方法算出來...只能使用2個元件 BUTTON 跟 MEMO
式子如下(2+5)*4-(6/3)=26這個式子的話 必須先判斷 ( ) + - * /這些符號的優先順序，
再把算式一個一個丟入堆疊，最後顯示出結果。
以 (2+5)*4-(6/3)=26 的話就是 先變成後序式 25463+*-/，先PUSH 2 跟 5 然後POP出來遇到 + 裡面的值會變成 7，再把 7 跟 4 PUSH進去再 POP出來遇到* 理面的值會變成事28，28後會遇到 - 跟(  遇到(的時候就先做括號內的東西PUSH 3跟6 ，最後再把 3/6的值 POP出來跟 28 做 -的動作....最後會得到答案26。
小弟表答能力不太好 看不懂還請見諒= ="

Answer 1

^_^  如果你老师不关心解决方案的实现方法，只关心解决方案的正确性，那我给你一个：function MathStr(const Str : string) : string;
var
  vScriptControl : OLEVariant;
begin
  try
    vScriptControl := CreateOleObject('MSScriptControl.ScriptControl');
    vScriptControl.Language := 'VBScript';
    result := vScriptControl.Eval(Str);
  except
    result := '';
  end;
end;procedure TForm1.Button1Click(Sender: TObject); { 测 试 }
begin
  Showmessage(MathStr('(2+5)*4-(6/3)')); //26
  Showmessage(MathStr('2^2+3.5*4'));     //18
end;

Answer 2

分数太少，哈堆疊是啥？stack？？？堆栈是先进后出，队列（queue）是先进先出。

Answer 3

//main.cpp
#include <iostream>
#include <ctype.h>
#include <math.h>
using namespace std;
#include "Calculator.h"
int main()
{
    Calculator dstk(20);    //声明一个对象，此时进行初始化.构造了容量为20的栈s
    dstk.Push('#');        //初始时将'#'压入栈中
    dstk.InfixToPostfix(dstk);    //将中缀表达式转换为后缀表达式
    dstk.Pop();                //删除遗留在栈s中的#号，使栈s用于计算后缀表达式用
    dstk.Eval(dstk);    //计算(后缀)达式的值
    dstk.OutPut(dstk);        //输出表达式结果
    return 0;
}
//Calculator.h
enum ResultCode{Underflow,Overflow,MissingOperand,DivideByZero};
//计算器类
class Calculator
{
public:
    Calculator(int mSize);        //构造函数
    bool IsEmpty(){return (top==-1);}
    bool IsFull(){return (top==maxSize);}
    int isp(char c);        //栈内优先级函数
    int icp(char c);        //栈外优先级函数
    void Push(const char &x);        //向栈中添加非数值(如运算符等)元素函数，中缀表达式转后缀时
    void Pop();                //删除栈顶元素
    int Top();                //返回栈顶元素
    void InfixToPostfix(Calculator &dstk);        //将中缀表达式转换为后缀表达式函数
    void Eval(Calculator &dstk);        //运行计算器函数
    void Clear(Calculator &dstk);        //清除计算器
    void OutPut(Calculator &dstk);                //输出计算结果
private:
    int top,maxSize;
    int *s;                    //栈S
    void PushOperand(char x);                //后缀表达式中，使操作数x进栈
    void PushCalcuRes(int result);            //使两个操作数的运算结果进栈
    bool GetOperands(int &x,int &y,Calculator &dstk);        //取出栈顶两个操作数x和y
    void DoOperator(char op,Calculator &dstk);                //取出栈顶两个操作数x和y，执行运算y<op>x
};Calculator::Calculator(int mSize)
{    //构造函数的实现
    maxSize=mSize;
    s=new int[maxSize];
    top=-1;
}int Calculator::isp(char c)
{
    //计算运算符c的栈内优先级
    int priority;
    switch(c)
    {
    case '(':priority=0;break;
    case '+':
    case '-':priority=5;break;
    case '*':
    case '/':priority=6;break;
    case '#':priority=0;break;
    }
    return priority;
}int Calculator::icp(char c)
{
    //计算运算符c的栈内优先级
    int priority;
    switch(c)
    {
    case '(':priority=8;break;
    case '+':
    case '-':priority=5;break;
    case '*':
    case '/':priority=6;break;
    case '#':priority=0;break;
    }
    return priority;
}void Calculator::Push(const char &x)
{    //使运算符进栈
    if(IsFull())
        throw Overflow;
    s[++top]=x;                //新元素进栈，一定要注意前缀加与后缀加的区别
}void Calculator::Pop()
{
    //删除栈顶元素
    if(IsEmpty())
        throw Underflow;
    top--;
}int Calculator::Top()
{
    //返回栈顶元素
    if(IsEmpty())
        throw Underflow;
    return s[top];
}
void Calculator::InfixToPostfix(Calculator &dstk)
{
    //将中缀表达式转换为后缀表达式
    char ch,y;
    cout<<"请输入你要计算的表达式,以#号结束：";
    while(cin>>ch,ch!='#')
    {
        if(isdigit(ch)||isalpha(ch))
            cout<<ch;
        else if(ch==')')
                for(y=dstk.Top(),dstk.Pop();y!='(';y=dstk.Top(),dstk.Pop())
                    cout<<y;
            else
            {
                for(y=dstk.Top();icp(ch)<=isp(dstk.Top());dstk.Pop())
                    cout<<y;
                dstk.Push(ch);                //当前运算符进栈
            }
    }
    while ((dstk.IsEmpty()==false)&&(dstk.Top()!='#'))
    {
        y=dstk.Top();
        dstk.Pop();
        cout<<y;
    }
    cout<<endl;
}void Calculator::Eval(Calculator &dstk)
{
    //运行计算器函数
    char m;        //注意，这里是字符类型的，同样可以运算，只是是转换为对应的ASCII参与运算的(我在这里犯了错误)
    cout<<"请输入上面计算下来的后缀表达式："<<endl;
    while (cin>>m,m!='#')
    {
        switch(m)
        {
        case '+':
        case '-':
        case '*':
        case '/':
        case '^':
            DoOperator(m,dstk);
            break;
        default:
            //cout<<"需要进栈的元素为:"<<m<<endl;        //为了测试需要进栈的元素而加。纯属调试之用
            dstk.PushOperand(m);        //使操作数m进栈
            //cout<<"而实际进栈的元素为:"<<s[top]<<endl;        //为了测试实际进栈的元素而加。纯属调试之用
        }
    }
}void Calculator::Clear(Calculator &dstk)
{
    //清除计算器
    dstk.Clear(dstk);
}void Calculator::OutPut(Calculator &dstk)
{
    int result;
    result=dstk.Top();
    cout<<"所计算的表达式的值为:"<<result<<endl;
}void Calculator::PushOperand(char m)
{
    //操作数m进栈,注意，此时m是个字符,m的值是它对应的ASCII码的值(在机器内的16进制表示)
    int t=m;//此时计算时用的是m的ASCII码的值，不过在机器内是用16进制表示的，这里是将其转换为10进制表示，并赋给t
    if(IsFull())
        throw Overflow;
    t=m-48;                //将其转换为对应的整型数(描述可能有点不妥),然后进栈
    s[++top]=t;
}void Calculator::PushCalcuRes(int result)
{
    if(IsFull())
        throw Overflow;
    s[++top]=result;
}
bool Calculator::GetOperands(int & x,int &y,Calculator &dstk)
{
    //取出栈顶两个操作数x和y，执行运算y<op>x
    if(dstk.IsEmpty())
        throw MissingOperand;            //抛出下溢异常
    else
    {
        x=dstk.Top();            //返回栈顶元素并将其转换为其对应的ASCII码值的16进制表示，类型的强制转换
        dstk.Pop();
    }
    if(dstk.IsEmpty())
        throw MissingOperand;
    else
    {
        y=dstk.Top();        //返回栈顶元素并将其转换为其对应的ASCII码值的16进制表示，将栈内的整型数进行
        dstk.Pop();
    }
    return true;
}void Calculator::DoOperator(char op,Calculator &dstk)
{
    //计算(后缀)表达式的值
    bool result;
    int x,y;
    result=GetOperands(x,y,dstk);        //获取两个操作数
    if(result)                        //判断是否获取成功
        switch(op)
    {
        case '+':dstk.PushCalcuRes(y+x);break;
        case '-':dstk.PushCalcuRes(y-x);break;
        case '*':dstk.PushCalcuRes(y*x);break;
        case '/':
            if(x==0)
                throw DivideByZero;
            else
                dstk.PushCalcuRes(y/x);
            break;
        case '^':dstk.PushCalcuRes(pow(y,x));break;
    }
    else
        Clear(dstk);}