stack.h
#ifndef STACK
#define STACK
#include "stdafx.h"
#include <cstdlib>
typedef struct stack {
double data;
struct stack *next;
}stack;
stack *init_stack()
{
stack *top;
top = (stack*)malloc(sizeof(stack));
top->next = NULL;
return top;
}
int isEmpty(stack *top)
{
if (top->next = NULL)
return 1;
else
return 0;
}
float push(stack *top, float x)
{
stack *p;
p = (stack*)malloc(sizeof(stack));
if (p == NULL)
return -1;
p->data = x;
p->next = top->next;
top->next = p;
return 0;
}
float pop(stack *top, float *x)
{
stack *p;
if (top->next == NULL)
return -1;
p = top->next;
*x = p->data;
top->next = p->next;
free(p);
return 0;
}
float getTop(stack *top)
{
float *x = NULL;
if (top->next == NULL)
return -1;
*x = top->next->data;
return *x;
}
#endif // !STACK
****## 算术表达式求值.cpp****
#include "stdafx.h"
#include
#include
#include "stack2.h"
#include
using namespace std;
class Calculator {
private:
stack *opnd;
stack *optr;
public:
Calculator();
virtual ~Calculator();
int getnext(int *n);
int getIndex(char a);
char operPrior(char a, char b);
float operation(float a, float operate, float b);
float evaluateEpression();
};
Calculator::Calculator() {
opnd = init_stack();
optr = init_stack();
}
Calculator::~Calculator() {
;
}
int Calculator::getnext(int n) {
char c;
*n = 0;
while ((c = getchar()) == ' ');
if ((!isdigit(c)) && (c != '+' || c != '-' || c != '' || c != '/' || c != '(' || c != ')' || c != '='))
{
throw ("表达式出错！");
}
else
{
push(optr, c);
n = c;
return 1;
}
do {
*n = *n * 10 + (c - '0');
c = getchar();
} while(isdigit(c));
cin.putback(c);
return 0;
}
int Calculator::getIndex(char a)
{
int i;
switch (a)
{
case '+':
i = 0; break;
case '-':
i = 1; break;
case '':
i = 2; break;
case '/':
i = 3; break;
case '(':
i = 4; break;
case ')':
i = 5; break;
case '=':
i = 6; break;
default:
break;
}
return i;
}
char Calculator::operPrior(char a, char b)
{
int i = getIndex(a);
int j = getIndex(b);
char pre[7][7] = {
{ '>','>','<','<','<','>','>' },
{ '>','>','<','<','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '>','>','>','>','<','>','>' },
{ '<','<','<','<','<','=','0' },
{ '>','>','>','>','0','>','>' },
{ '<','<','<','<','<','0','=' }
};
return pre[i][j];
}
float Calculator::operation(float a, float operate, float b)
{
float result = 0.0;
switch ((int)operate)
{
case '+':
result = a + b; break;
case '-':
result = a - b; break;
case'*':
result = a * b; break;
case '/':
result = a / b; break;
default:
break;
}
return result;
}
float Calculator::evaluateEpression()
{
int flag = 0;
char priorChar;
int ch;
float *x = NULL;
char prior;
float left, right;
float operate;
float *top;
push(optr, '=');
priorChar = '=';
flag = getnext(&ch);
while (getTop(optr) != '=' || ch != '=')
{
if (!flag)
{
push(opnd, ch);
priorChar = '0';
flag = getnext(&ch);
}
else
{
priorChar = ch;
if ((priorChar == '=' || priorChar == '(') && (ch == '+' || ch == '-'))
{
push(opnd, 0);
priorChar = '0';
}
prior = operPrior(getTop(optr), ch);
switch (prior)
{
case '<':
push(optr, ch);
flag = getnext(&ch);
break;
case '>':
if (isEmpty(opnd))
throw ("表达式出错！");
pop(opnd, &right);
if (isEmpty(opnd))
throw ("表达式出错！");
pop(opnd, &left);
pop(optr, &operate);
push(opnd, operation(left, operate, right));
flag = getnext(&ch);
break;
case '=':
pop(optr, &operate);
flag = getnext(&ch);
break;
case '0':
throw ("表达式出错！");
break;
default:
break;
}
}
}
pop(opnd, x);
return *x;
}
int main()
{
Calculator calcuExpression;
float result = 0.0;
result = calcuExpression.evaluateEpression();
cout << result << endl;
return 0;
}
